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

===========================  25.2.2009  ===========================

Symbol, abeceda, slovo, jazyk, konečná reprezentace.
Reprezentace pomocí generování a rozpoznávání.
Příklad nedeterministických algoritmů pro generování a rozpoznávání symetrických slov.
Zmínka o třídě NP a problému P=?NP.
Generativní systém pro slova a^n b^n.
Zadáno cvičení: Generativní systém pro slova a^n b^n c^n.
Chomského hierarchie.
Složitost úloh
  - test příslušnosti daného slova do jazyka
  - test ekvivalence dvou reprezentací jazyků
  pro různé třídy v Chomského hierarchii.

===========================  4.3.2009  ===========================

Regulární gramatika, přechodový diagram, konečný automat.
Příklady
 L_11 = |w|_a sudé
 L_12 = |w|_b sudé
 L_1 = L_11 průnik L_12
 L_2 = L_11 sjednocení L_12
 L_3 = |w|_b - |w|_a dělitelný 3

===========================  11.3.2009  ===========================

Řešení příkladu nalézt kontextovou gramatiku pro a^n b^n c^n.
Příklady:
  PD pro slova obsahující "aba".
  KA pro slova obsahující "aba", pomocí komplementu pak slova neobsahující "aba".
  PD pro slova obsahující "ababc".
  Obecný algoritmus na nalezení KA pro slova končící daným podslovem. Ukázka na
    slově "ababc".
Zadáno na příště:
  PD a KA pro slova obsahující "aba" nebo "bab". Pomocí komplementu pak KA pro
  slova neobsahující ani "aba" ani "bab".
  KA nebo PD pro slova v abecedě a,b,c,d, která v úsecích mezi výskytem "a"
  a výskytem "c" neobsahují "b".

===========================  18.3.2009  ===========================

Řešení příkladů z předchozí hodiny.
Ekvivalence PD a KA pomocí podmnožinové konstrukce.

===========================  25.3.2009  ===========================

Zavedení vlastních regulárních jazyků a regulárních výrazů.
Příklady RV pro jazyky
  sudá délka
  délka dělitelná 10
  |w|_a sudé
  |w|_a i |w|_b sudé
Příklad na důkaz rovnosti jazyků (b + eps)(a + ab)^*, (a + ba)^*(b + eps)
Dokázáno, že ke každému RV existuje ekvivalentní PD.

===========================  1.4.2009  ===========================

Přednáška se nekonala.

===========================  8.4.2009  ===========================

Příklad nalezení ekvivalentního RV pro daný KA.
Důkaz, že ke každému KA existuje ekvivalentní RV.
Množinové operace s jazyky definovanými KA.
Test neprázdnosti pro PD.
Sloučením předchozích postupů dostáváme test ekvivalence dvou KA nebo,
  obecněji, libovolných dvou reprezentací regulárních jazyků.
Ekvivalence slov podle jazyka.
Dolní odhad počtu stavů KA podle počtu tříd ekvivalence.
Příklad neregulárního jazyka a^i b^i.
Cvičení: Nalezněte co nejmenší KA pro jazyk slov w = x_1 x_2 ... x_n,
  které splňují podmínku x_{n-k} = a v abecedě {a,b}. Dokažte, že
  je minimální pomocí ekvivalence na slovech.

===========================  15.4.2009  ===========================

Dořešen příklad se slovy x_1 ... x_n splňujícími x_{n-k} = a.
Připomenutí bezkontextových gramatik, relace odvozování, derivační strom.
Každý reulární jazyk je bezkontextový.
Nevypouštějící gramatika, ke každé G existuje nevypouštějící G' tak, že L(G') = L(G) - eps .

===========================  22.4.2009  ===========================

Připomenutí transformace gramatiky na nevypouštějící.
Ukázka konstrukce gramatiky rekurzivním rozkladem slov
  v jazyce slov se stejným počtem výskytů a,b.
Chomského normální forma, ke každé nevypouštějící gramatice
existuje ekvivalentní gramatika v Chomského normální formě.

===========================  29.4.2009  ===========================

Uzavřenost bezkontextových jazyků na sjednocení, zřetězení a iteraci.
Neuzavřenost na průnik.
Uzavřenost na průnik s regulárním jazykem.
Věta o nahrazení. Použití na důkaz, že slova a^ib^ic^i netvoří bezkontextový jazyk.