PRŮBĚH PŘEDNÁŠKY FORMÁLNÍ JAZYKY A AUTOMATY (ZIMNÍ SEMESTR 2014/2015)

===========================  7.10.2014  ===========================

Symbol, abeceda, slovo, jazyk, zřetězení jazyků, iterace.
Konečná reprezentace jazyka pomocí nedeterministického generování,
speciálně pomocí opakování substitucí podle přepisovacích pravidel.
Příklady (bezkontextových) gramatik pro jazyky
 - symetrická slova sudé délky
 - správně uzávorkované výrazy
Cvičení: Najít nekonečný jazyk L_1 tak, aby pro libovolné
jazyky L_2 a L_3 platila implikace
  L_1 L_2 = L_1 L_3  =>  L2 = L3

===========================  4.11.2014  ===========================

Přechodové diagramy (PD), konečné automaty (KA), regulární výrazy (RV).
Každý KA lze převést na ekvivalentní PD bez podstatné změny velikosti.
Každý RV lze převést na ekvivalentní PD při nejvýše lineárním zvětšení.
Ke každému PD lze sestrojit ekvivalentní KA exponenciální velikosti.

===========================  11.11.2014  ===========================

Ke každému PD lze sestrojit ekvivalentní RV exponenciální velikosti.
Operace s jazyky reprezentovanými pomocí KA, test ekvivalence KA.
Ekvivalence slov podle jazyka.
Počet tříd ekvivalence slov podle jazyka je dolní odhad počtu stavů KA.
Příklad neregulárního jazyka.
Každý KA pro jazyk (a+b)^*a(a+b)^{k-1} má alespoň 2^k stavů.
Cvičení:
 - dokažte, že každý KA pro jazyk (aa)^ + (aaa)^* má alespoň 6 stavů
 Najděte KA pro jazyky
 - slova splňující |w|_b liché => |w|_a liché
 - slova splňující (|w|_b - |w|_a) je dělitelné 3

===========================  18.11.2014  ===========================

Zavedení bezkontextové gramatiky, relace odvození, jazyk reprezentovaný
  gramatikou, derivační strom.
Jazyk slov tvaru a^ib^i je bezkontextový.
Poznámky bez důkazu:
  Jazyk slov tvaru a^ib^ic^i a jazyk slov tvaru ww nejsou bezkontextové.
  Průnik dvou bezkontextových jazyků nemusí být bezkontextový.
  Průnik bezkontextového jazyka a regulárního jazyka je bezkontextový.
Každý regulární jazyk je bezkontextový.
Z gramatiky lze efektivně odstranit neterminály, které se nevyskytují
  v odvození žádného slova.
Probrána cvičení z předchozí hodiny.
Další cvičení:
(4) Dokažte a(ba + a)^* = (ab + a)^*a .
(5) Nalezněte co nejmenší KA a RV pro jazyk slov nad abecedou
    {a_1, ..., a_k}, která obsahují každý symbol právě jednou.

===========================  25.11.2014  ===========================

Ke každé bezkontextové gramatice existuje nevypouštějící gramatika
  generující stejný jazyk kromě prázdného slova.
Bezkontextové jazyky jsou uzavřeny na sjednocení, zřetězení a iteraci.
Průnik bezkontextového a regulárního jazyka je bezkontextový jazyk.
Cvičení:
Probrán důkaz a(ba + a)^* = (ab + a)^*a .
Nalezněte RV pro jazyk slov v abecedě {a,b}, která obsahují sudý počet
  výskytů "a" a sudý počet výskytů "b".

===========================  2.12.2014  ===========================

Ke každé BG existuje ekvivalentní gramatika neobsahující pravidla A -> B.
Ke každé BG, která negeneruje prázdné slovo, existuje ekvivalentní
  gramatika v Chomského normální formě.
Cvičení:
Nalezněte BG pro jazyky
L_1 = {a^i b^j ; i \le 2j}
L_2 = {a^i b^j ; i \not= j}
L_3 = {a^i b^j c^k ; j = i+k }

===========================  16.12.2014  ===========================

Věta o nahrazení.
Jazyky {a^i b^i c^i | i \ge 1} a {ww | w \in {a,b}^*} nejsou
  bezkontextové.
Postův korespondenční problém.
Následující úlohy jsou algoritmicky nerozhodnutelné:
 - zjistit, zda průnik dvou bezkontextových jazyků je neprázdný,
 - zjistit, zda bezkontextová gramatika generuje všechna slova
   v dané abecedě.