PRŮBĚH PŘEDNÁŠKY FORMÁLNÍ JAZYKY A AUTOMATY (ZIMNÍ SEMESTR 2012/2013)
=========================== 10.10.2012 ===========================
Konečná abeceda, slovo, jazyk.
Zřetězení jazyků, asociativita, iterace jazyka.
u \in X, u \not\in L neimplikují L různé od LX.
Příklad X = {eps, a}, L = ba^*.
Konečná reprezentace jazyka pomocí generování nebo rozpoznávání.
Nedeterministický algoritmus, příklady generování a rozpoznávání
symetrických slov.
Generativní systém definující jazyk a^n b^n, n \ge 0.
Obousměrný deterministický automat se zásobníkem může rozpoznávat
symetrická slova.
=========================== 17.10.2012 ===========================
Dvojcestný zásobníkový automat pro symetrická slova.
Příklad L = LX, když X={eps, u} a slovo u nepatří do L.
Uvažujeme gramatiku G, jejíž terminální abeceda je \Sigma, neterminální abeceda
je \Gamma a počáteční symbol je S \in \Gamma.
Odvozovací pravidlo je tvaru \alpha -> \beta, kde \alpha a \beta jsou slova
ve sjednocení terminální a neterminální abecedy a \alpha obsahuje alespoň jeden
neterminál.
Relace => a její iterace =>^*.
Jazyk definovaný gramatikou je L(G) = {u \in \Sigma^*; S =>^* u}
Důkaz korektnosti generativního systému pro jazyk a^n b^n, n \ge 0.
Chomského hierarchie, postupné omezování tvaru pravidel.
Třída 0, částečně rekurzivní jazyky, libovolná pravidla s neprázdnou
levou stranou.
Třída 1, kontextové jazyky. Jsou to jazyky rozpoznatelné nebo
generovatelné nedeterministickýcm TS (Turingův stroj) s lineárním
omezením prostoru. Deterministicky vyžadují kvadratický prostor,
ale již se nejedná o charakterizaci. Pravidla gramatiky mají
pravou stranu alespoň tak dlouhou jako levou stranu. Bez újmy na
obecnosti lze požadovat, aby pravidla byla tvaru x A y -> x \beta y.
Od tohoto tvaru pravidel je odvozen název kontextové gramatiky.
Třída 2, bezkontextové gramatiky. Pravidla jsou tvaru A -> \beta.
Třída 3, regulární gramatiky. Pravidla jsou některého z tvarů
A -> a B
A -> eps
Stejnou třídu jazyků dostaneme pro zobecněné regulární gramatiky,
které mají pravidla tvaru
A -> \beta B
A -> \beta
kde \beta je libovolné slovo v terminální abecedě.
Cvičení. Rozšiřte gramatiku pro {a^n b^n} na gramatiku pro {a^n b^n c^n}.
=========================== 24.10.2012 ===========================
Řešení úlohy o generování jazyka a^i b^i c^i.
Složitost testování w \in L(G) a L(G_1) = L(G_2) na různých stupních Chomského hierarchie.
Kontextové jazyky jsou právě rovny jazykům rozpoznatelným nedeterministickým Turingovým
strojem v lineárním prostoru, tedy prostoru O(n), kde n je délka vstupního slova.
Zavedení Turingova stroje (TS) pomocí přechodové funkce, programovací jazyk pro TS.
Příklad TS pro kopírování slova na dvou páskách a jedné pásce.
=========================== 31.10.2012 ===========================
Program na kopírování slova na jedné pásce TS.
Konfigurace TS zapsaná pomocí slova v konečné abecedě.
Důkaz uzavřenosti třídy NSPACE(s(n)) na komplement (Immerman).
Zavedení přechodových diagramů, definice přijímaného jazyka.
=========================== 7.11.2012 ===========================
Ekvivalence základních a rozšířených regulárních gramatik.
Zavedení speciálních regulárních gramatik, které jsou zobecňují základní regulární
gramatiky a jsou speciálním případem rozšířených regulárních gramatik.
Mezi speciálními regulárními gramatikami a přechodovými diagramy existuje bijekce,
která zachovává definovaný jazyk. Z toho plyne, že regulární gramatiky všech tří
typů a přechodové diagramy definují stejnou třídu jazyků.
Definice konečného automatu a konečného automatu s výstupem.
Cvičení: Nalezeněte automat s výstupem, který rozlišuje typy čísel ve zdrojovém
kódu programu.
=========================== 14.11.2012 ===========================
Dokončen automat pro rozpoznávání čísel.
Popsány regulární výrazy a jazyk, který reprezentují.
Příklady převodu PD na KA pro jazyk (a+b)^* a (a+b)^k a pro jazyk slov obsahujících ababc.
KA lze přímočaře převést na ekvivalentní PD.
Popsána podmnožinová konstrukce KA k libovolnému PD, důkaz jejich ekvivalence příště.
=========================== 21.11.2012 ===========================
Důkaz podmnožinové konstrukce KA k danému PD.
Důkaz ekvivalence PD a RV.
Cvičení. Najděte RV pro KA popsaný některou z tabulek
a b c
1 2 1 3
2 1 3 2
3 3 2 1
a b
1 2 3
2 1 4
3 4 1
4 3 2
V obou případech je počáteční stav 1 a množina přijímajících stavů {1}.
=========================== 28.11.2012 ===========================
Neprobrali jsme cvičení z minula.
Poznámka: astronomický jev 21.12.2012.
Ekvivalence KA a RV.
Operace s jazyky reprezentovanými KA.
Test neprázdnosti jazyka definovaného PD a test ekvivalence KA.
Neregulární jazyky, pumpovací lemma a třídy ekvivalence slov podle jazyka.
Důkaz exponenciální velikosti KA pro (a+b)^*a(a+b)^k.
Příklad bezkontextové gramatiky.
=========================== 5.12.2012 ===========================
Dokončení příkladů z minula.
Příklad slova, které nelze odvodit v gramatice pro aritmetické výrazy.
Bezkontextové jazyky jsou uzavřeny na sjednocení, zřetězení a iteraci.
Definice nevypouštějící gramatiky, ke každé gramatice G existuje nevypouštějící
gramatika reprezentující jazyk L(G) - {eps}.
Chomského normální forma, ke každé gramatice G existuje gramatika v Chomského
normální formě reprezentující jazyk L(G) - {eps}.
Věta o nahrazení (pumping lemma, uvwxy theorem) a použití pro důkaz, že jazyk
a^i b^i c^i není bezkontextový.
=========================== 12.12.2012 ===========================
Cvičení. Rozhodněte, které z následujících jazyků jsou bezkontextové.
(1) správná uzávorkování pomocí závorek ([ podle parity hloubky vnoření
(2) výrokové formule
(3) pravdivé výrokové formule
Jazyky slov tvaru a^i1 b^i2 c^i3 nebo a^i1 b^i2 c^i3 d^i4 zadané abecedou a
podmínkami na exponenty.
(4) abcd, i1 <= 2 i2, i2 <= 2 i3, i3 <= 2 i4, i4 <= 2 i1
(5) abcd, i1 <= 2 i2, i2 <= 2 i3, i3 <= 2 i4
(6) abc, i1 <= 2 i2, i2 <= 2 i3
Cvičení. a^i1 b^i2 c^i3 d^i4 s podmínkami
(1) i1 = i2, i3 = i4
(2) i1 = i3, i2 = i4
(3) i1 = i4, i2 = i3
=========================== 19.12.2012 ===========================
Příklad konstrukce lineární gramatiky pro jazyk slov tvaru "u^R,v",
kde čárka je prvek abecedy, u,v jsou slova z {0, 1}^* a platí
hodnota(v) = hodnota(u) + 1 a hodnota(u) \ge 1, kde zápisem hodnota(u)
rozumíme přirozené číslo, které je ve dvojkové soustavě zapsané
slovem u. Požadujeme, že slova u, v nezačínají číslicí 0. Slovo u^R
je reverze slova u, tedy slovo zapsané s opačným pořadím symbolů.
Lineární gramatika je taková, že v každé větné formě odvoditelné
v dané gramatice je nejvýše jeden neterminál.
Konstrukce proběhla v několika krocích
(a) KA s výstupem, který dostává na vstup dvojice binárních číslic
slov u, v počínaje nejnižším řádem (tedy od konce) a počítá binární
zápis rozdílu v - u, opět od nejnižších řádů.
(b) KA, který rozpoznává dvojice slov u, v splňující podmínku
hodnota(v) = hodnota(u) + 1.
(c) Přepsání získaného KA jako obrácené regulární bezkontextové gramatiky, která
generuje dvojice slov tak, že generuje slova v abecedě dvojic symbolů.
Například slovo 11 10 10 01 10 00 00 10 representuje dvojici slov
1 1 1 0 1 0 0 1, 1 0 0 1 0 0 0 0, kde první slovo je tvořené prvními
symboly z každé dvojice, druhé slovo je tvořeno druhými symboly z každé
dvojice.
(d) Bezkontextová gramatika byla dále upravena opět na lineární gramatiku, ale
tak, že první symboly z generovaných dvojic byly generovány za neterminálem
a druhé symboly byly generovány před neterminálem.
=========================== 2.1.2013 ===========================
Konstrukce bezkontextové gramatiky pro komplement jazyka výpočtů TS.
Důsledek. Otázka, zda L(G) = \Sigma^* pro obecnou bezkontextovou
gramatiku G, je algoritmicky nerozhodnutelná.
Výpočet součtu součinů číslic k ciferných čísel. Zobecnění pomocí
grafů pro libovolnou podmnožinu definovanou regulárním jazykem.