Surynek 16.6.2015

Základní přednáška z teorie jazyků a automatů. Důraz je kladen na seznámení se základními pojmy a fakty (konečné a zásobníkové automaty, Turingovy stroje, regulární, bezkontextové a kontextové gramatiky).
VImpaler
Matfyz(ák|ačka) level I
Příspěvky: 3
Registrován: 26. 5. 2015 14:18
Typ studia: Informatika Bc.

Surynek 16.6.2015

Příspěvek od VImpaler »

\left\{a^ib^j\:|\: 1\le i\le j \right\} (nedá sa regulárne pumpovať, existuje bezkontextová gramatika)

Kontextové jazyky a lineárne obmedzené Turingove stroje.

Odporúčania na skúšku: Cvičenie je najlepšie mať u Surynka, pretože robí tie úlohy na zaradenie do Chomského hierarchie (rovnaké alebo podobné). Pred skúškou si teda je dobré prejsť všetky tie príklady na jeho stránke.
Ely
Matfyz(ák|ačka) level I
Příspěvky: 3
Registrován: 3. 2. 2015 19:11
Typ studia: Informatika Bc.

Re: Surynek 16.6.2015

Příspěvek od Ely »

Zařadit jazyk:
L = \{ ucv | u,v \in \{a,b\}, |u|=|v|\}
Poté otázka na vztah kontextových a lineárních gramatik a dokázat.


řešení:
jazyk je bezkontextový, (dokonce deterministický i bezprefixový) - např. zkonstruovat zásobník

Co jsem slyšela u ostatních:

L = \{ ucv | u,v \in \{a,b\}, u 
eq v\}

Otázky na Postův korespondenční problém, regulární pumping lemma, něco na Turingův stroj.
Odpovědět

Zpět na „TIN071 Automaty a gramatiky“