V ěta

2.3.4.

Každý

regulárni jazyk je

rozpoznatelný

konečným

automatem. D ů k a z . P r o libovolnou konečnou abecedu 27 se s n a d n o se­ strojí a u t o m a t y rozpoznávající jazyky 0 a {a} p r o každé a e 27. V ěta je tedy přímým důsledkem vět 2.2.11 a 2.2.15 o uzavře­ nosti 3 F v ůči regulárním operacím. P oznámka 2.3.5. Důkazy vět 2.3.4, 2.2.11 a 2.2.15 naznačují, ž e každý regulárni výraz a lze převést na nedeterministický a u t o ­ mat s i r ozpoznávající [ a ] a přitom takový, že počet stavů a u t o ­ m a t u s i n ebude příliš převyšovat počet symbolů obsažených v a. V elikost s i v z ávislosti na a můžeme o d h a d n o u t p o m ě r n ě přesně: K aždý z elementárních jazyků {a} (a e 27) lze reprezentovat ne­ deterministickým a u t o m a t e m o nejvýše d v o u stavech, jazyky {e} a 0 a u t o m a t y s jedním stavem. D ů k a z y vět 2.2.11 a 2.2.15 pak u kazují, že p o k u d regulárním výrazům a, /? odpovídají po ř a d ě n edeterministické a u t o m a t y o m a n stavech, lze sestrojit nede­ terministické a u t o m a t y reprezentující [a + /?] a [a/?], z nichž k aždý má m + n s tavů. Automat reprezentující [ a * ] b u d e mít m + 1 s tavů. Z vláštní význam, dodává regulárním výrazům skutečnost, že j imi lze zadat každý jazyk rozpoznatelný konečným a u t o m a t e m . V ěta 2.3.6. regulárni. Každý jazyk rozpoznatelný konečným automatem je

D ů k a z . Buď s i = (Q,27,ô,qv F ) k onečný a u t o m a t rozpozná­ vající L. N echť Ô = { <?„-,<?„}• P r o každé i, j (1 § i', j Ś n) d efinujme »
R

í "r.

ä

1

^

ij = { w e 2 ľ * ; % . , w ) = q,.},

t j. j a k o množinu slov, která převádějí a u t o m a t ze stavu q, do s tavu q ľ Z řejmě platí, že
w

k^) = l = U f R H 94