P řiklad 2.1.5. Jazyk z př. 2.1.1 je rozpoznáván nedeterminis­ tickým a u t o m a t e m z obr. 20. S rovnejte, jak odpovídá struktura zadání jazyka v př. 2.1.1 se s trukturou diagramu na obr. 20. K r o m ě t o h o si na obrázku p o -

C;—• °> io
1

* 0 1

*—• 1 í

*-"uo,i

O
0,1

v šimněte ještě j e d n o h o zajímavého rysu plynoucího z definice 2.1.4. Z některých vrcholů diagramu vychází méně než dvě Šipky. T o je zcela korektní, protože podle definice 2.1.2 přiřazuje pře­ chodová funkce každé dvojici z Q x 27 jistou m n o ž i n u p o k r a č o ­ váni. T a k é například p r á z d n o u množinu. P o k u d m á t e pochyb­ nosti, jaký vliv má na přijetí slova výpočet, který t a k t o uvázne v n ěkterém stavu, vraťte se k definici 2.1.4 a znovu si ji pro­ myslete. N a každý konečný a u t o m a t lze pohlížet j a k o na speciální p řípad nedeterministického konečného a u t o m a t u . P r o t o každý j azyk rozpoznatelný deterministickým konečným a u t o m a t e m je t aké rozpoznatelný a u t o m a t e m nedeterministickým. Důležité je, ž e platí i obrácené tvrzení. V ěta nečným ným 2.1.6. Každý jazyk také rozpoznatelný rozpoznatelný nedeterministickým deterministickým ko­

automatem je automatem.

koneč­

V d ůkazu věty se používá tzv. p o d m n o ž i n o v é k o n s t r u k c e . T uto k onstrukci si nejprve objasníme na intuitivní úrovni. C hceme-li se přesvědčit, zda určitý nedeterministický konečný : m a t přijímá d a n é slovo, nemusí n a m á t k o v é hledání v ta­ b a k ę či stavovém diagramu vést k cíli a je třeba postupovat nějjakym systematickým způsobem. Například si lze na stavovém Ä g r a m u a u t o m a t u označit hracími kameny všechny stavy, d o f caerých se a u t o m a t mohl na základě dosud přečteného úseku