Kleene tétele

Kleene tételének fő tézise : "A reguláris halmazok és az automata nyelvek osztályai egybeesnek."

Megfogalmazás

Legyen tetszőleges ábécé. A nyelv akkor és csak akkor része a reguláris nyelvek ábécében való félbesorolásának, ha ezt valamilyen véges automata megengedi. $V={a_{{1}},...,a_{{n}}}$ $L\subseteq V^{{*}}$ $R(V)$ $V$

Bizonyítás

Bármely állapotgép átmenet gráf mindig ábrázolható normalizált formában, amelyben csak egy kezdeti csúcs van csak kimenő élekkel és csak egy végső csúcs csak bejövő élekkel.

A normalizált formában bemutatott átmeneti gráfon két redukciós művelet végezhető el - élcsökkentés és csúcsredukció - az átmeneti gráf által megengedett nyelv megőrzése mellett. Minden redukciós művelet nem változtatja meg az átmeneti gráf által felismert nyelvet, hanem csökkenti vagy az élek számát, vagy a csúcsok számát.

Ezért minden automata nyelv reguláris halmaz.
Minden R reguláris kifejezéshez készíthető egy véges automata (esetleg nem determinisztikus), amely felismeri az R által megadott nyelvet. Az ilyen automatákat rekurzívan fogjuk definiálni.

Ezért minden reguláris halmaz automata nyelv. A tétel bizonyítást nyert.

Linkek

Karpov Yu. G. Az automaták elmélete. - Szentpétervár: Péter, 2002. S. 224. ISBN 5-318-00537-3

Lásd még

Irodalom

Belousov A. I., Tkachev S. B. Diszkrét matematika. - M. : MGTU, 2006. - 744 p. — ISBN 5-7038-2886-4 .