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

==================  4.10.2005  ===================

Symbol, abeceda, slovo, jazyk, třída jazyků.
Značení pro prázdné slovo, délku slova, zřetězení slov.
Konečná reprezentace jazyka, rozpoznávání, generování, determinismus, nedeterminismus.
Příklad nedeterministického generování a rozpoznávání symetrických slov.
Definice konečného automatu s výstupem a pro rozpoznávání.
Příklad rozlišování typů čísel v textu programu.

Domácí cvičení: odstranit předpoklad, že před i za desetinnou tečkou musí být číslice.
Požadováno jen to, aby byla před nebo za desetinnou tečkou.

Zmínka o dalších typech reprezentace: přechodový diagram a regulární výraz.
Všechny tři reprezentace (spolu s konečným automatem) jsou ekvivalentní (definují
stejnou třídu jazyků), ale jsou velké rozdíly v efektivitě (úspornosti) reprezentace.

Zatím vynechána formální definice přijetí slova konečným automatem.

==================  11.10.2005  ===================

Dokončen výklad konečného automatu (KA).
Vyloženy regulární výrazy (RV) a přechodové diagramy (PD).
Ukázány různé reprezentace jazyků (a+b+c)^*abc(a+b+c)^* a a^*b^*c^*.
Cvičení:
(1) rozhodnout, zda existují jazyky L_1, L_2 a L_3 splňující
  L_1 neprázdný a konečný
  L_1 L_2 = L_1 L_3
  L_2 \not= L_3
(2) Dokázat asociativitu zřetězení jazyků.

==================  18.10.2005  ===================

Příklad konečných neprázdných jazyků L_1, L_2, L_3, které splňují
L_1 L_2 = L_1 L_3, ale L_2 \not= L_3.

Zřetězení jazyků je asociativní operace.

Probrána cvičení: Najít KA a RV pro
1. sudá slova
2. slova délky dělitelné 3
3. slova, jejichž délka je dělitelná 2 nebo 3.

Domácí cv: Dokažte, že pokud žádné slovo L_1 není prefixem jiného slova L_1,
ale L_1 je neprázdný, pak L_1 L_2 = L_1 L_3 implikuje L_2 = L_3.

==================  25.10.2005  ===================

Dokázáno, že pro neprázdný bezprefixový L_1 platí
   L_1 L_2 = L_1 L_3  =>  L_2 = L_3

Probrána cvičení: Najít KA a RV pro jazyk slov w, která splňují
4. |w|_a je sudé
5. |w|_a je liché
6. |w|_b liché => |w|_a je liché
7. |w|_b liché a zároveň |w|_a je liché
Pro 6,7 zatím jen KA. Pro RV dán návod použít výraz ((r^* s r^* s)^* r^* s r^*)
a rozklad slova na aa,ab,ba,bb

==================  1.11.2005  ===================

Vyřešena cvičení
- najít RV pro jazyky (6) a (7), trik se substitucí, jazyky L_00, L_01, L_10, L_11.
- najít KA pro jazyky (8) a (9). Neřešeny RV.
Probrána dělitelnost n = 3, 9, 11, 5 počítaná pomocí zbytků 10^i mod n.

Domácí cvičení: počet slov délky 100 neobsahujících bab, ab..., ...ba.

==================  8.11.2005  ===================

Dán návod jak řešit příklad s počtem slov bez osamocených a.
Nalezeny RV pro jazyky (6) a (7) (k rozmyšlení zbylo nalézt úspornější způsob).
Nalezen KA pro jazyk slov dělitelných 7 vyjádřenými desítkovými číslicemi 0,1,2.
Nalezen KA pro jazyk slov obsahujících ababc.
Jako domácí cvičení zbývá dokončit obecný algoritmus konstrukce automatu pro
   slova obsahující předem dané slovo u = a_1 a_2 ... a_k.
   Stavy jsou prefixy u, tj. \eps, a_1, a_1 a_2, ..., a_1 a_2 ... a_k.
   Pokud a = a_{i+1}, pak víme
   delta(a_1 a_2 ... a_i, a) = a_1 a_2 ... a_i a_{i+1}
   Zbývá případ, když a \not= a_{i+1}

==================  15.11.2005  ===================

Hodina odpadla.

==================  22.11.2005  ===================

Dokončena konstrukce automatu pro vyhledávání daného podslova ve vstupním slově.
Ekvivalence PD a RV.
KA je speciálním případem PD.
Idea konstrukce KA ekvivalentního danému PD.

==================  29.11.2005  ===================

Ke každému PD existuje ekvivalentní KA.
Konstrukce některých jazyků R^k_ij pro přechodový diagram D určený hranami
1 -> 2 "a"
2 -> 1 "a"
1 -> 3 "b"
3 -> 1 "b"
2 -> 3 "c"
3 -> 2 "c"
a s počátečním a koncovým vrcholem 1.

==================  6.12.2005  ===================

Dokončení RV pro přechodový diagram D z předchozí hodiny.
KA pro jazyk (a+b)i^*a(a+b).
KA pro jazyk slov obsahujících aba nebo bab (nedokončeno).

==================  13.12.2005  ===================

Dokončení KA pro jazyk slov obsahujících aba nebo bab.
Konstrukce KA pro sjednocení, průnik, rozdíl a symetrický rozdíl jazyků reprezentovaných KA.
Klasifikace Booleovských spojek dvou proměnných (2 konstanty, 4 funkce jedné
proměnné, 4 funkce typu konjunkce, 4 funkce typu disjunkce a 2 funkce typu parity)

Zadána úloha nalezení počtů slov dané délky v jednotlivých stavech KA pro jazyk
slov v abecedě {a,b} bez samostatných symbolů a.

==================  20.12.2005  ===================

Neregulární jazyky.
Bezkontextové gramatiky, množina neterminálů, pravidla, krok odvození, odvození,
derivační strom, L(G), příklad gramatiky pro výrazy.
Každý regulární jazyk je bezkontextový.
Nevypouštějící gramatika, Chomského normální forma.
Věta uvwxy (o nahrazení) a její aplikace.
Jazyk {a^i b^i c^i, i \ge 0} není bezkontextový.
Jazyk {a^i b^j c^k, i \le 2j, j \le 2k, k \le 2i} není bezkontextový.

==================  3.1.2006  ===================

Bezkontextové jazyky jsou uzavřeny na sjednocení, zřetězení a iteraci.
Průnik bezkontextového jazyka a regulárního je bezkontextový (bez dk).
Příklad dvou bezkontextových jazyků, jejichž průnik není bezkontextový.
Věta: Pro žádnou ze tří podmínek
  1. L(G_1) = L(G_2)
  2. L(G_1) = \Sigma^*
  3. L(G_1) průnik L(G_2) = prázdná množina
neexistuje algoritmus, který by platnost dané podmínky rozhodl pro libovolné
dvě zadané gramatiky G_1, G_2 (nebo libovolnou G_1 v případě podmínky 2).
Důkaz se dělá pomocí algoritmické nerozhodnutelnosti problému zastavení daného
programu na daných datech, ale nebyl vyložen.
Ke každé nevypouštějící gramatice existuje ekvivalentní gramatika
v Chomského normální formě.
Důkaz věty o nahrazení.
Rozhodněte, které z následujících jazyků jsou bezkontextové (všude se předpokládá,
že i, j, k jsou nezáporná přirozená čísla)
  1. {a^i b^j c^k ; j = i+k}
  2. {a^i b^j c^k d^l ; i=l a j=k}
  3. {a^i b^j c^k d^l ; i=k a j=l}
  4. {a^i b^j c^k d^l ; i=j a k=l}
  5. {a^{i^2}}
  6. slova v abecedě {a,b,c} se stejným počtem výskytů a,b,c
  7. {a^i b^j c^k ; max{i,j,k} \le 4/9 (i+j+k)}