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

===========================  11.10.2016  ===========================

Obecný úvod, symbol, abeceda, jazyk, gramatika.
Příklad kontextové gramatiky pro jazyk a^ib^ic^i.
Bezkontextová gramatika pro jazyk symetrických slov sudé
délky (s důkazem) a pro Dyckův jazyk (zatím bez důkazu).

===========================  18.10.2016  ===========================

Nevypouštějící bezkontextová gramatika.
Gramatika pro Dyckův jazyk.
Levá větná forma, derivační strom.
Obecný pojem automatu.
Nedeterministický zásobníkový automat pro obecný bezkontextový jazyk (nedokončeno).
K otázce významu teorie formálních jazyků: tato otázka je kladena šířeji.
Jde o klasickou součást základu teoretické informatiky, ale tuto roli postupně
ztrácí a stává se z ní speciální obor, viz například

Do results have a “teach-by-date?”.

Výklad regulárních a bezkontextových jazyků patří do oblasti základních
výpočetních modelů. Těchto modelů je více a budu rozšiřovat výklad o další
modely, například booleovské, a výklad regulárních a bezkontextových jazyků
bude stručnější.

===========================  25.10.2016  ===========================

Program pro TS, který rozpoznává symetrická slova sudé délky, a konstrukce
přechodové funkce pro řídící jednotku TS na základě tohoto programu.
Zavedení značení g = O(f), g = \Omega(f), g = \Theta(f).
Binární zápis přirozeného čísla n má délku ceiling(log_2(n + 1)).
TS pro rozpoznávání jazyků {a^ib^i ; i \ge 0} a {a^ib^ic^i ; i \ge 0} současně
v čase O(n) a prostoru O(log n) a důkaz dolního odhadu \Omega(log n) pro
prostorovou složitost.

Zmínka o třídách L=DSPACE(log n) a NL=NSPACE(log n).
Úloha s,t-souvislost orientovaného grafu patří do třídy NL a není obtížné ukázat,
že z toho plyne, že patří do třídy DSPACE(log^2 n).
Pro speciální případ neorientovaných grafů patří tato úloha do L, což bylo dokázáno
v roce 2008 (zde) po předchozích odhadech
O(log^{4/3} n) z roku 2000 a
O(log^{3/2} n) z roku 1989.

===========================  1.11.2016  ===========================

Nedeterministický zásobníkový automat, který simuluje levé derivace pro danou
bezkontextovou gramatiku.
Připomenutí zavedení regulárních výrazů (RV).
Konečný automat (KA) jako speciální případ TS a definice pomocí přechodové funkce
a zobecněné přechodové funkce.
Příklad KA pro výpočet zbytku modulo m pro číslo v číselné soustavě se základem b.
Přechodový diagram (PD) jako zobecnění zápisu KA pomocí grafu.
Reverze jazyka reprezentovaného KA je vyjádřitelná pomocí PD.

===========================  8.11.2016  ===========================

Připomenutí přechodových diagramů (PD).
Ekvivalence KA a PD, ekvivalence RV a PD.
Množinové operace a test rovnosti pro jazyky reprezentované KA.
Bezkontextová gramatika pro konstantní výrokové formule s danou hodnotou.
Každý regulární jazyk je bezkontextový.
Ke každé bezkontextové gramatice existuje nevypouštějící gramatika, která
  reprezentuje stejný jazyk kromě prázdného slova (důkaz nedokončen).