| 1.10.2002
|
- pojmy abeceda, symbol, slovo, prázdné slovo, délka slova, jazyk.
- konečný automat, příklady jazyků rozpoznatelných konečným automatem.
- ekvivalence slov podle jazyka, důkaz toho, že jazyk dobrých uzávorkování
není rozpoznatelný konečným automatem.
|
| 8.10.2002
|
- zopakování pojmů symbol, slovo, jazyk, zaveden pojem třídy jazyků.
- konečná reprezentace jazyka, rozpoznávání jazyka, generování jazyka,
determinismus, nedeterminismus.
- Mealyho a Mooreův automat, věta o jejich ekvivalenci.
- začátek příkladu s rozpoznáváním čísel
|
| 15.10.2002
|
- dokončení příkladu s rozpoznáváním čísel.
- umocňování jazyků.
- cvičení: Vennův diagram čtyř speciálních tříd jazyků.
- zavedení regulárních jazyků, regulárních výrazů a jejich interpretace.
- cvičení na reg. výrazy.
- zbývá rozhodnout, zda (rs+r)^*r = r(sr+r)^*.
|
| 22.10.2002
|
- Dokázáno (rs+r)^*r = r(sr+r)^*.
- RV a KA pro slova obsahující abc.
- Vysvětlena podmnožinová konstrukce.
- RV a KA pro slova obsahující ababc.
- RV a KA pro slova obsahující všechny symboly tříprvkové abecedy.
- Zadán příklad s L_min, L_max.
|
| 29.10.2002
|
- Rozebrán příklad L_min, L_max.
- Ke každému KA existuje ekvivalentní PD.
- Navrhli jsme konstrukci KA pro libovolný PD a dokázali pomocné
tvrzení o přechodové funkci tohoto automatu.
|
| 5.11.2002
|
- Dokončení důkazu ekvivalence PD a KA z podmnožinové konstrukce.
- Ke každému RV existuje ekvivalentní PD.
- Ke každému PD existuje ekvivalentní RV.
|
| 12.11.2002
|
- Odhad velikosti RV z Kleeneovy konstrukce.
- RV k automatu pro jazyk slov v {a,b} se sudým počtem a i b.
- Úprava výsledného RV a důkaz její korektnosti.
|
| 3.12.2002
|
- Průnik, rozdíl a doplněk jazyků reprezentovaných KA.
- Test ekvivalence a neprázdnosti.
- Pokračování unixových regulárních výrazů.
|
| 10.12.2002
|
- Bezkontextová gramatika, jazyk přijímaný bezkontextovou gramatikou.
- Nevypouštějící gramatika.
- Každý regulární jazyk je bezkontextový, jazyk a^ib^i je bezkontextový.
|