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.