Kleenen lause

Kleenen lauseen päätees on : " Säännöllisten joukkojen ja automaattikielten luokat ovat samat."

Sanamuoto

Antaa olla mielivaltainen aakkoset. Kieli on osa aakkosten säännöllisten kielten puoliksi muodostumista, jos ja vain jos jokin äärellinen automaatti sen sallii. $V={a_{{1}},...,a_{{n}}}$ $L\subseteq V^{{*}}$ $R(V)$ $V$

Todiste

Mikä tahansa tilakoneen siirtymägraafi voidaan aina esittää normalisoidussa muodossa, jossa on vain yksi alkupiste, jossa on vain lähtevät reunat ja vain yksi loppupiste, jossa on vain sisääntulevia reunoja.

Normalisoidussa muodossa esitetylle siirtymägraafille voidaan suorittaa kaksi pelkistysoperaatiota - reunan pienennys ja huippupisteen pienennys - samalla kun säilytetään tämän siirtymägraafin sallima kieli. Jokainen pelkistystoiminto ei muuta siirtymägraafin tunnistamaa kieltä, vaan vähentää joko reunojen tai kärkien määrää.

Siksi jokainen automaattinen kieli on säännöllinen joukko.
Jokaiselle säännölliselle lausekkeelle R voidaan rakentaa äärellinen (mahdollisesti epädeterministinen) automaatti, joka tunnistaa R:n määrittämän kielen. Määrittelemme tällaiset automaatit rekursiivisesti.

Siksi jokainen tavallinen joukko on automaattikieli. Lause on todistettu.

Linkit

Karpov Yu. G. Automaattiteoria. - Pietari: Pietari, 2002. S. 224. ISBN 5-318-00537-3

Katso myös

Kirjallisuus

Belousov A. I., Tkachev S. B. Diskreetti matematiikka. - M .: MGTU, 2006. - 744 s. — ISBN 5-7038-2886-4 .