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.