Diagonální jazyk, Univerzální TM, algoritmicky nerozhodnutelné problémy, Postův korespondenční problém

 12. video přednáška

Kontextové a monotónní gramatiky a lineárně omezené automaty, diagonální a univerzální jazyk

Důležité znát: definice, věty, umět napsat kontextovou/monotónní gramatiku k uvedeným a velmi podobným jazykům, případně popsat Turingův stroj dané jazyky přijímající (většinou mi stačí vámi vybraná metoda, zvlášť když znáte větu přijímá lin. omez. aut. právě když existuje kontextová gramatika.

Diagonální a univerzální jazyk.

Je toho hodně, jak jsem ostatně měla dojem v 1:08:17.  

Opravy k řeči, slajdy jsou pokud vím dobře:

8:45  a^nb^nC^n není bezkontextový, je kontextový.
33:27 generuji monotónní gramatiku, kterou z předchozího umím přepsat na kontextovou.

48:29 jsou rekruzivní, nejsou KONTEXTOVÉ, JSOU rekurzivně spočetné. Obrázek správně.
58:43 přijímá nulu, ne prázný řetězec (to by musel přijmout po přečtení blank, 000)

1:04-1:08:17 lze přeskočit, nevěřte mi že 1:08:17 přednáška končí ;-))