Průběh přednášky a cvičení Formální jazyky a automaty

9.10.2001
  • symbol, slovo, jazyk.
  • prázdné slovo, délka slova, zřetězení slov.
  • konečná reprezentace jazyka (přijímání/generování jazyka, deterministický/nedeterministický algoritmus).
  • příklad nedeterministického přijímání palindromů pomocí zásobníku.
  • možnosti chápání složitosti reprezentace
    1. deskriptivní (délka programu);
    2. výpočtová (počet kroků nebo paměť potřebná pro výpočet);
    3. omezení prostředků pro přijímání/generování (tuto budeme studovat ve fja).
  • zařízení s konečnou pamětí
    1. konečný automat s výstupem Mealyho typu;
    2. konečný automat s výstupem Mooreova typu;
    3. konečný automat (pro rozpoznávání jazyka).
16.10.2001
  • cvičení na konstrukci konečných automatů.
  • zadána úloha najít automat pro průnik dvou jazyků, pro které již automaty máme.
23.10.2001
  • dokončení konečného automatu: zobecněná přechodová funkce, L(M), příklad "sudý počet výskytů a,b".
  • zřetězení, umocňování a iterace jazyků.
  • definice regulárních jazyků pomocí sjednocení, zřetězení a iterace z konečných jazyků, definice regulárního výrazu a jeho interpretace.
  • příklad vyjádření jazyka "sudý počet výskytů a,b" pomocí regulárního výrazu.
  • definice přechodového diagramu pomocí orientovaných grafů s násobnými hranami a smyčkami, w-cesta, L(D).
  • zadána cvičení
    1. důkaz asociativity zřetězení jazyků.
    2. ekvivalence (s + ls*l)*s* = (s*ls*l)*s*
30.10.2001
  • cvičení na konstrukci KA a RV.
  • asociativita zřetězení jazyků.
  • na rozmyšlení: RV pro jazyk slov obsahujících všechny symboly abecedy.
6.11.2001
  • algoritmus na zjištění dosažitelnosti v grafu.
  • Postův korespondenční problém.
  • operace s jazyky zadanými jako PD: sjednocení, zřetězení, iterace.
  • zadáno k rozmyšlení: důkaz správnosti konstrukce pro iteraci.
13.11.2001
  • rozbor důkazu konstrukce PD pro iteraci jazyka.
  • pro A bez prázdného slova má rovnice AX+B=X právě jedno řešení.
  • vyjádření jazyka {w; w obsahuje podslovo "ababc"} pomocí RV,PD a KA.
  • případ KA ponechán jako cvičení.
20.11.2001
  • důsledek předchozí věty: ke každému RV existuje ekvivalentní PD.
  • věta: ke každému PD existuje ekvivalentní RV.
  • diskuse velikosti získaného RV.
  • připomenuto: každý KA lze při vhodném přeznačení považovat za ekvivalentní PD.
  • věta: ke každému PD existuje ekvivalentní KA.
    V důkazu věty nedokončen indukční krok, tj. že z (*) pro w plyne (*) pro wa.
27.11.2001
  • dokončen důkaz věty, že ke každému PD existuje ekvivalentní KA.
  • cvičení:
    • KA,PD pro L=(a+b)^2a(a+b)^*
    • KA,PD pro L^R
    • dokažte, že kvocient regulárních jazyků je opět regulární (algoritmus pomocí paralelního běhu automatů).
11.12.2001
  • KA a PD pro komplement, průnik a rozdíl regulárních jazyků.
  • test neprázdnosti jazyka a ekvivalence jazyků reprezentovaných KA nebo PD.
  • ekvivalence slov podle jazyka, charakterizace regulárních jazyků.
  • příklad neregulárního jazyka.
  • dolní odhad počtu stavů KA.
17.12.2001
  • bezkontextová gramatika, odvození podle gramatiky, jazyk definovaný bezkontextovou gramatikou, derivační strom.
  • sjednocení, zřetězení a iterace bezkontextových jazyků je bezkontextový jazyk (pro iteraci jen konstrukce gramatiky).
8.1.2002
  • dokončen důkaz pro iteraci bezkontextového jazyka.
  • průnik bezkontextového a regulárního jazyka je bezkontextový (bez důkazu).
  • nevypouštějící gramatika, ke každé bezkontextové gramatice existuje nevypouštějící gramatika ekvivalentní až na prázdné slovo.
  • Chomského normální forma, ke každé gramatice existuje gramatika v Chomského normální formě, která je ekvivalentní až na prázdné slovo.
  • formulována věta o nahrazení (důkaz je v textech webu).
  • jazyk {a^i b^i c^i; i ge 0} není bezkontextový.
  • jazyk slov v tříprvkové abecedě se stejným počtem výskytů všech symbolů není bezkontextový.