PRŮBĚH PŘEDNÁŠKY FORMÁLNÍ JAZYKY A AUTOMATY (LETNÍ SEMESTR 2007/2008)

===========================  20.2.2008  ===========================

Přednáška se nekonala.

===========================  27.2.2008  ===========================

Pojmy symbol, abeceda, slovo, jazyk.
Studujeme jazyky s konečnou reprezentací.
Příklad nedeterministického algoritmu pro generování
a pro rozpoznávání jazyka symetrických slov.
Rozbor přepisovacího systému
S -> ABS
S -> \epsilon
BA -> AB
BS -> b
Bb -> bb
Ab -> ab
Aa -> aa
Indukcí dokázáno, že každé odvoditelné slovo obsahuje stejný počet
symbolů z {a,A} a z {b,B} a má jeden z tvarů:
  {A,B}^*S
  {A,B}^*a^ib^j
Každé terminální odvoditelné slovo je tedy tvaru a^nb^n.
Navíc, každé takové slovo je odvoditelné.
Uvedený přepisovací systém lze rozšířit na generování a^nb^nc^n.

===========================  5.3.2008  ===========================

Přednáška se nekonala.

===========================  12.3.2008  ===========================

Chomského hierarchie
Složitost algoritmického zjištění w \in L(G), L(G_1) = L(G_2),
Problém w \in L(G) je algoritmicky rozhodnutelný pro typ 1,2,3.
Složitost pro typ 1 je exponenciální, pro typ 2 O(n^3), pro typ 3 je O(n),
kde n je délka vstupního slova a reprezentace jazyka je pevně dána.
Problém L(G_1) = L(G_2) je algoritmicky rozhodnutelný jen pro typ 3.
Konstrukce gramatik (přechodových diagramů) pro jazyky v následující tabulce
  Abeceda   Podmínka na slova
  a,b       |w|_a sudé
  a,b       |w|_a sudé, |w|_b sudé
  a         |w|_a dělitelné 3
  a,b       |w|_a - |w|_b dělitelné 3
Nedokončené příklady
  a,b       |w|_a >= 1, |w|_b >= 1
  a,b,c     |w|_a >= 1, |w|_b >= 1, |w|_c >= 1
  a         |w|_a dělitelné 2 nebo dělitelné 3

===========================  19.3.2008  ===========================

Dokončení příkladů
  w \in {a,b}, |w|_a \ge 1, |w|_b \ge 1
  w \in {a,b,c}, |w|_a \ge 1, |w|_b \ge 1, |w|_c \ge 1
  délka w dělitelná 2 nebo 3
Zavedení zobecněných regulárních gramatik.
Zavedení přechodových diagramů (PD) a konečných automatů (KA).
Důkaz ekvivalence zobecněných regulárních gramatik a PD.
Příklad s klasifikací čísel v programovacím jazyce.
Zadán příklad jazyka
  w \in {a,b,c}, w obsahuje podslovo ababc
Je třeba ještě ukázat reprezentaci tabulkou a v obou příkladech
porovnat složitost reprezentace pomocí KA a PD.

===========================  26.3.2008  ===========================

Probrán příklad na nalezení PD a KA pro jazyk slov obsahujících ababc.
Formulován obecný algoritmus konstrukce KA pro hledání jednoho slova.
Podmnožinová konstrukce KA, který je ekvivalentní zadanému DP.
Zbývá důkaz ekvivalence zkonstruovaného KA a původního PD.

===========================  2.4.2008  ===========================

Dokázáno, že podmnožinová konstrukce dává KA, který je ekvivalentní výchozímu PD.
Příklad s reverzí jazyka {w \in {a,b}^*, druhý symbol je a}.
Domácí cvičení: Najděte KA pro reverzi jazyka {w \in {a,b}^*, třetí symbol je a}.

===========================  9.4.2008  ===========================

Přednáška se nekonala.

===========================  16.4.2008  ===========================

De Bruijnův graf pro slova délky 3 ve dvouprvkové abecedě.
Regulární jazyky, regulární výrazy, ekvivalence PD a RV.
Zmínka o zápisu regulárních výrazů v editoru vim.

===========================  23.4.2008  ===========================

PD a KA pro jazyk (b + eps)(a + ab)^*.
Test neprázdnosti jazyka daného KA.
Test ekvivalence jazyků daných KA, případně PD, RV.
Ekvivalence slov podle jazyka, dolní odhad počtu stavů automatu.
Důkaz, že a^ib^i není regulární.
Věta o pumpování pro regulární jazyky (název nebyl při přednášce uveden).

===========================  30.4.2008  ===========================

Cvičení. Najít gramatiku pro
1. uzávorkované výrazy reprezentující binární stromy
2. všechny uzávorkované výrazy
3. všechny uzávorkované výrazy se střídajícími se závorkami () a [] podle hloubky.

Každý regulární jazyk je bezkontextový.
Bezkontextové jazyky jsou uzavřené na sjednocení, zřetězení a iteraci.
Bezkontextové jazyky nejsou uzavřené na průnik a rozdíl.
Postupná transformace obecné bezkontextové gramatiky na gramatiku, která je
 - nevypouštějící (pro jazyk po případném odebrání prázdného slova)
 - bez pravidel typu A -> B
 - bez pravidel s pravou stranou s terminály i neterminály
 - v Chomského normální formě
(Takto byl důkaz vyložen, ale je v něm chyba, protože jsme
určitý typ pravidel nevzali v úvahu. Najdete který?)

Cvičení na doma. Rozhodnout, které z následujících jazyků jsou regulární.
 - { a^ib^j ; i \equiv j (mod 3)}
 - { a^ib^j ; i \le j }
 - { a^{i^2} ; i \ge 0}

===========================  7.5.2008  ===========================

Vyřešení příkladů na regulární jazyky z minule.
Věta o nahrazení pro bezkontextové jazyky.
Příklady na rozhodování, které jazyky jsou bezkontextové:
  a^ib^jc^kd^l při různých podmínkách na i,j,k,l, konkrétně
    i=j and k=l
    i=k and j=l
    i=l and j=k
  w \in {a,b}^*, |w|_a = |w|_b
  w \in {a,b,c}^*, |w|_a = |w|_b = |w|_c