Matematické Fórum

Řekněme, že první jazyk je rozpoznáván automatem A. Zaveďme automat A', který obsahuje všechny stavy  A a s každým přechodem z Q1 do Q2 pomocí symbolu s v automatu A obsahuje A' přechody  z Q2 do Q1 pomocí všech symbolů abecedy. Krom stavů A obsahuje A' i svůj vlastní počáteční stav, z nějž vedou pouze eps. přechody, a to do všech stavů, které byly v A přijímající. Po 0 načtených znacích je A současně ve všech stavech, z nichž se do přijímajících stavů A dalo dostat 0 kroky. Po načtení  1 znaku se přesune do všech těch stavů, z nichž se dalo do přijímajících dostat 1 krokem, atd.

Spus?me nyní oba automaty nad týmž slovem. Slovo bude toto jejich spojení akceptovat, pokud se A nachází v některém ze stavů v nichž se nachází A'. Proč toto funguje? Pokud se načtením i znaků dostal první automat do stavu Qi a druhý do množiny stavů, která Qi obsahuje, znamená to, že po načtení dalších i znaků se A dostane do přijímajícího stavu, tedy že teď je v půlce nějakého slova.

Teď zbývá nahlédnout, že paralelní spojení deterministického a nedeterministického automatu je stejně silné, jako jeden deterministický. To by mělo být ve skriptech, která jsem tu na fóru už někde odkazoval (zkus když tak najít sám).