Kleene's theorem

The main thesis of Kleene’s Theorem : “The classes of regular sets and automaton languages coincide.”

Content

Wording

Let be $V={a_{1},...,a_{n}}$ ${\ displaystyle V = {a_ {1}, ..., a_ {n}}}$ - an arbitrary alphabet. Tongue $L\subseteq V^{*}$ ${\ displaystyle L \ subseteq V ^ {*}}$ is an element of the semiring of regular languages $R(V)$ ${\ displaystyle R (V)}$ in the alphabet $V$ ${\ displaystyle V}$ if and only if it is allowed by some finite state machine.

Proof of Kleene's theorem

Any transition graph of a finite state machine can always be represented in normalized form, in which there is only one initial vertex with only outgoing edges and only one final vertex with only incoming edges.

Over the transition graph presented in normalized form, two reduction operations can be performed — edge reduction and vertex reduction — while preserving the language allowed for this transition graph. Each reduction operation does not change the language recognized by the transition graph, but reduces either the number of edges or the number of vertices.

Therefore, each automaton language is a regular set.
For each regular expression R, a finite automaton (possibly non-deterministic) can be constructed that recognizes the language given by R. We will give a definition of such automata recursively.

Therefore, every regular set is an automaton language. The theorem is proved.

Links

Karpov Yu. G. Theory of automata. - St. Petersburg: Peter, 2002.P. 224. ISBN 5-318-00537-3

Literature

Belousov A.I., Tkachev S. B. Discrete mathematics. - M .: MSTU, 2006 .-- 744 p. - ISBN 5-7038-2886-4 .