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čí ;-))

13. video přednáška Nerozhodnutelné problémy

Důkazy propojují myšlenky dohromady, doporučuji shlédnout celé. To co bych ráda, abyste z přednášky znali, je v náledujcících minutách:
0-7:00
Nerozhodnutelné problémy, redukce problému
12:45-22:46
Problém zastavení (Halting problém), Postův korespondenční problém (PCP)
1:01:14-1:25:17
Věta: PCP je nerozhodnutelný. (důkaz před tím přeskočen)
Rozhodnutelné a nerozhodnutelné problémy pro bezkontextové gramatiky.