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

===========================  12.10.2011  ===========================

Jazyk, slovo, abeceda.
Prázdné slovo, zřetězení slov, délka slova, podslovo, prefix.
Zřetězení jazyků, asociativita zřetězení, iterace jazyka.
Reprezentace pomocí 
 - rozpoznávání,
 - generování.
Rozpoznávání může být realizováno obecným deterministickým algoritmem, ale
používají se i specializované automaty.
Pro generování se používají především systémy přepisovacích pravidel.
Příklad systému pro generování symetrických slov.
Cvičení.
1. Dokažte, že systém s počátečním symbolem S a přepisovacími pravidly

S -> ABS
S -> eps
BA -> AB
BS -> b
Bb -> bb
Ab -> ab
Aa -> aa

generuje jazyk {a^n b^n; n \ge 0}
2. Rozšiřte systém tak, aby generoval jazyk {a^n b^n c^n; n \ge 0}.

===========================  19.10.2011  ===========================

Řešení cvičení 1 z minulé hodiny.
Jazyky typu 0 a 1 v Chomského hierarchii.
Popsán Turingův stroj.

===========================  26.10.2011  ===========================

Gramatiky typu 2 (bezkontextové) a typu 3 (regulární).
Přechodový diagram. Ekvivalence s regulárními gramatikami.
Příklad na analýzu čísel ve zdrojovém textu programu.

===========================  2.11.2011  ===========================

Převod KA na ekvivalentní PD.
Transformace PD na ekvivalentní KA pomocí podmnožinové konstrukce.
Zavedení regulárních jazyků a regulárních výrazů.
Regulární výrazy reprezentují právě regulární jazyky.
Převod RV na ekvivalentní PD s lineárním nárůstem velikosti.
Převod PD na ekvivalentní RV s exponenciálním nárůstem velikosti.

===========================  9.11.2011  ===========================

Operace s jazyky vyjádřenými KA.
Test neprázdnosti a ekvivalence pro jazyky vyjádřené KA.
Ekvivalence slov podle jazyka, příklad neregulárního jazyka.
Příklad bezkontextové gramatiky pro jednoduché aritmetické výrazy.
Nevypouštějící gramatika.
Ke každé bezkontextové gramatice existuje nevypouštějící gramatika, která
reprezentuje právě všechna neprázdná slova generovaná původní gramatikou.
Chomského normální forma.
Ke každé bezkontextové gramatice existuje ekvivalentní gramatika, která
neobsahuje pravidla s jedním neterminálem na pravé straně.

===========================  16.11.2011  ===========================

Ke každé bezkontextové gramatice negenerující prázdné slovo existuje
ekvivalentní gramatika v Chomského normální formě.
Věta o nahrazení.
Jazyk {a^i b^i c^i; i \ge 0} není bezkontextový.

===========================  23.11.2011  ===========================

Přednášky od 23.11. do 21.12. se nekonaly.

===========================  4.1.2012  ===========================

Algoritmus rozpoznávání pro bezkontextovou gramatiku v čase n^3.
Zmínka o souvislosti s násobením matic, Strassenův algoritmus.
Turingův stroj, abeceda pásky, vstupní abeceda, konfigurace.
Příklad programu pro TS a jeho překlad na přechodovou funkci.
Jazyk výpočtů TS s reverzí sudých konfigurací.
Jazyk výpočtů TS je průnikem dvou bezkontextových jazyků.
Důsledek. Otázka neprázdnosti průniku dvou bezkontextových jazyků je
algoritmicky nerozhodnutelná.
Jazyk výpočtů TS je komplement bezkontextového jazyka.
Důsledek. Otázka, zda bezkontextová gramatika generuje všechna slova
v dané abecedě je algoritmicky nerozhodnutelná.