PR�B�H P�EDN��KY FORM�LN� JAZYKY A AUTOMATY (ZIMN� SEMESTR 2004/2005)

==================  12.10.2004  ===================

Symbol, abeceda, slovo, z�et�zen� slov, d�lka slova, pr�zdn� slovo.
Jazyk, t��da jazyk�, kone�n� reprezentace jazyka.
Generov�n� versus rozpozn�v�n� jazyka symetrick�ch slov nedeterministick�m algoritmem.
Kone�n� automaty s v�stupem a pro rozpozn�v�n�, p��klad s ��sly v programu.
Nedokon�ena rozpozn�vac� verze automatu a zobecn�n� p�echodov� funkce.

==================  19.10.2004  ===================

P��klad se zbytkem p�i d�len� 7 v des�tkov� soustav�.
Z�et�zov�n� a iterace jazyk�.
Regul�rn� jazyky, regul�rn� v�razy, jazyk je regul�rn�
pr�v� kdy� je vyj�d�iteln� regul�rn�m v�razem.
P��klady:
 - L_1 = slova sud� d�lky
 - L_2 = slova obsahuj�c� ababc
 - L_3 = slova obsahuj�c� aaa nebo bbb
 - L_4 = slova d�lky sud� nebo d�liteln� 3
 - L_5 = slovo obsahuj�c� n�jak� po�et symbol� a a za nimi
         n�jak� po�et symbol� b.
 - L_6 = n�kolik slov z jazyka L_5 odd�len�ch symboly c
 - L_7 = slova se sud�m po�tem v�skyt� symbolu a
 - L_8 = slova se sud�m po�tem v�skyt� symbolu a i b.

==================  26.10.2004  ===================

KA pro L_1 = slova sud� d�lky.
Definice roz���en� p�echodov� funkce a L(M).
KA pro jazyky L_2,...,L_8.
Zaveden� p�echodov�ch diagram�, w-cesty a L(D) pro diagram D.
Ka�d� regul�rn� jazyk lze vyj�d�it PD.
Formulov�na v�ta, �e ke ka�d�mu PD existuje ekvivalentn� RV
a definov�ny jazyky R_ij^k.

==================  2.11.2004  ===================

Ke ka�d�mu PD existuje ekvivalentn� RV (dokon�en� d�kazu)
Odhad d�lky z�skan�ho RV.
Ke ka�d�mu KA existuje ekvivalentn� PD.
Ke ka�d�mu PD existuje ekvivalentn� KA (podmno�inov� konstrukce).
Regul�rn� jazyky jsou uzav�eny i na pr�nik, rozd�l a dopln�k.
Test nepr�zdnosti L(D) - formulace algoritmu, ale zat�m bez d�kazu.

==================  9.11.2004  ===================

Dokon�en� testu nepr�zdnosti L(D).
Test ekvivalence D_1 a D_2 (tj. test, zda L(D_1) = L(D_2)).
Pr�nik, sjednocen� a rozd�l jazyk� vyj�d�en�ch KA.
Ekvivalence slov podle jazyka, p��klad neregul�rn�ho jazyka.
Jazyk je regul�rn� pr�v� kdy� m� jemu p��slu�n� ekvivalence
   jen kone�n� po�et t��d, bez d�kazu.
P��klad jazyka s exponenci�ln�m po�tem stav� KA.
Cvi�en� (budu ps�t (a+b)* misto (a+b)^*:
1. KA pro (a+b)^ka(a+b)*
2. KA a RV pro jazyk L_2 = {w \in {a,b,c}^*; w obsahuje v�echny symboly abecedy}
3. Plat� rovnost (a + ba*b)*a* = (a*ba*b)*a* ?
4. Plat� rovnost (ab + a)*a = a(ba + a)* ?
5. Pro jazyk L definujme
   L_min = {u \in L; ��dn� vlastn� prefix u nepat�� do L}
   L_max = {u \in L; ��dn� vlastn� prodlou�en� u nepat�� do L}
   Doka�te, �e pro regul�rn� L jsou i L_min a L_max regul�rn�

==================  16.11.2004  ===================

�e�en� p��klad� z minula.
Podmno�inov� konstrukce a sou�in automat�
na p��klad� jazyka slov obsahuj�c�ch pr�v�
jedno ze slov aba, bab.
P��klady generov�n� a^ib^i a dobr�ch uz�vorkov�n�.
Obecn� bezkontextov� gramatika, odvozov�n�, jazyk
definovan� b.g.
Deriva�n� strom na p��klad� jednoduch�ch v�raz�.
Formulov�na v�ta, �e ka�d� regul�rn� jazyk je
bezkontextov�.

==================  23.11.2004  ===================

Dokon�en� d�kazu, �e ka�d� regul�rn� jazyk je bezkontextov�.
Ke ka�d� bezkontextov� gramatice G existuje nevypou�t�j�c�
  gramatika G' tak, �e L(G') = L(G) - {\epsilon}.
Sjednocen�, z�et�zen� a iterace bezkontextov�ch jazyk� je
  bezkontextov� jazyk.
Pr�nik bezkontextov�ho jazyka L a regul�rn�ho jazyka R je bezkontextov�.
  Zkonstruov�na gramatika G' a dok�z�no, �e 
  w \in L(G') => w \in L a w \in R
  V d�kazu w \in L a w \in R => w \in L(G') je pot�eba 
  roz���it ohodnocen� stav� z list� stromu do vnit�n�ch uzl�.

==================  30.11.2004  ===================

Dokon�en� bezkontextovosti pr�niku bezkontextov�ho a regul�rn�ho jazyka.
Zaveden� Chomsk�ho norm�ln� formy.
Z gramatiky lze eliminovat pravidla typu A -> B.
Ke ka�d� gramatice existuje gramatika v Chomsk�ho norm�ln� form�, kter� generuje
stejn� jazyk a� na pr�zdn� slovo.
V�ta o nahrazen� (uvwxy-v�ta, v�ta o pumpov�n�), aplikace na jazyk a^i b^i c^i.
P��klady jazyk�, kter� nejsou bezkontextov�:
  a^i b^j c^k ; 0 <= i <= 2j, 0 <= j <= 2k, 0 <= k <= 2i.
  a^{i^2} ; i >= 0.
P��klady jazyk�, kter� jsou bezkontextov�:
  a^i b^j c^k; i=j+k
  a^i b^j c^k; j=i+k
  a^i b^j c^k d^l; i=l, j=k
  a^i b^j c^k d^l; i=j, k=l

==================  14.12.2004  ===================

Vy�e�eny p��klady z minula (1-4).
Dal�� p��klady:
5. gramatika pro logick� v�razy.
6. gramatika pro logick� v�razy s hodnotou 1.
7. L = {w \in (a+b)*; |w|_a = |w|_b}
8. L = {w \in (a+b)*; 2|w|_a = |w|_b}

==================  21.12.2004  ===================

Cvi�en�. Rozhodn�te, kter� z n�sleduj�c�ch jazyk�
jsou bezkontextov�.
L_1 = {ww; w \in (a+b)*}
L_2 = {w#w^R#w; w \in (a+b)*}
L_3 = (a+b+#)* - L_2
L_4 = {a^ib^j; i \not= j}
L_5 = {a^ib^j; i \not= j, i \not= 2j}
L_6 = {a^ib^jc^k; i < j < k}
L_7 = {a^ib^j; j = i^2}
L_8 = {a^i; i je prvo��slo}

==================  4.1.2005  ===================

Cvi�en�. Do�e�eny p��klady L_1, ..., L_8.
Dal�� p��klady.
Rozhodn�te, kter� z n�sleduj�c�ch jazyk� jsou regul�rn�:
L_9 = {x \in (a+b)*; x=x^R}
L_10 = {xwx^R; w,x \in (0+1)+}
L_11 = {xx^Rw; w,x \in (0+1)+}
Nedo�e�en L_11.