Studijní materiály

Zpět

Hromadně přidat materiály

Předtermin_21_05_2008

IB005 - Formální jazyky a automaty I

Hodnocení materiálu:

Zjednodušená ukázka:

Stáhnout celý tento materiál

ˇnku.
(g) Existuje rekurzivnˇe spoˇcetn´y jazyk, jehoˇz doplnˇek je rekurzivn´ı.
(h) Pro kaˇzd´y rekurzivnˇe spoˇcetn´y jazyk R existuje nˇej´ak´y Turing˚uv stroj, kter´y cykl´ı pr´avˇe
nad slovy z R.
(i) Pro kaˇzd´y rekurzivnˇe spoˇcetn´y jazyk R existuje nˇej´ak´y Turing˚uv stroj, kter´y cykl´ı pr´avˇe
nad slovy, kter´a nejsou z R.
(j) Probl´em zastaven´ı nen´ı ani ˇc´asteˇcnˇe rozhodnuteln´y.
4. (10 bod˚u) Koneˇcn´y automat, kter´y je zadan´y n´ıˇze uvedenou tabulkou, minimalizujte a
v´ysledn´y minim´aln´ı automat s tot´aln´ı pˇrechodovou funkc´ı zapiˇste v kanonick´em tvaru.
a b c
→1 3 6 8
2 4 2 2
3 7 5 -
←4 4 4 4
5 7 5 4
6 5 5 -
7 7 7 4
8 8 - 8
5. (15 bod˚u)
(a) Definujte Post˚uv korespondenˇcn´ı probl´em (PKP) a inici´aln´ı PKP (inPKP).
(b) Dokaˇzte, ˇze inPKP je nerozhodnuteln´y.

Stáhnout celý tento materiál

Předchozí

1 2 3

Vloženo: 25.04.2009

Velikost: 49,06 kB

Stáhnout celý tento materiál

Komentáře

Tento materiál neobsahuje žádné komentáře.