Question

Show that a set recognized by a finite-state automaton is regular. (This is the if part of Kleene’s theorem.)

Short answer

A set recognized by a finite-state automaton is regularis proved as true.

Step-by-step solution

General form

Finite-state automaton (Definition):A finite-state automata \({\bf{M = }}\left( {{\bf{S,I,f,}}{{\bf{s}}_{\bf{0}}}{\bf{,F}}} \right)\) consists of an initial or start state \({{\bf{s}}_0}\), a finite set S of states, a finite alphabet of inputs I, a transition function f that assigns a future state to each pair of state and input (such that \({\bf{f:S \times I}} \to {\bf{S}}\)), and a subset F of S made up of final states (or accepting states).

Regular expressions (Definition):A recursive definition of the regular expressions over a set I is as follows:

The symbol \(\emptyset \) is a regular expression;

The symbol \({\bf{\lambda }}\)is a regular expression;

whenever \({\bf{x}} \in {\bf{I}}\); the symbol x is a regular expression.

The abbreviations \(\left( {{\bf{AB}}} \right){\bf{,}}\left( {{\bf{A}} \cup {\bf{B}}} \right){\bf{,}}\) and \({\bf{A*}}\) are also regular expressions when A and B are.

Regular sets are the sets that regular expressions represent.

Kleene’s theorem:A finite-state automaton can only recognise a set as regular if and only if it can.

Theorem 2: A set is formed by a regular grammar if and only if it is a regular set.

Rules of regular expression represents a set:

\(\emptyset \)represents the string-free set, or the empty set;

\({\bf{\lambda }}\)represents the set \(\left\{ {\bf{\lambda }} \right\}\), which is the set containing the empty string;

The string having the symbolxin it is represented by the set \(\left\{ {\bf{x}} \right\}\);

(AB) depicts the order of the sets that are represented by both A and B;

The combination of the sets that both A and B represent is represented by \(\left( {{\bf{A}} \cup {\bf{B}}} \right)\);

The Kleene closure of the sets that A represents is represented by \({\bf{A*}}\).

Step 2: Proof of the given statement

Given that, the Kleene’s theorem.

To prove: a set recognized by a finite-state automaton is regular.

Proof:

Each terminal string in the automata has a unique derivation, and the construction of the regular grammar reflects this. (Each regular sub-expression has a unique machine, as shown in the proof of the theorem "A set if formed by a regular grammar if and only if it is a regular set.")

Additionally, the automata generate the non-empty strings that will be used to drive the machine to its final state.

By making the start state a final state, the empty string will only be accepted if it is also included in the language. Notably, the start state is not the final state for any of the other submachines provided in the proof.(With the exception of \({\bf{1*}}\), which has a string value of \({\bf{\lambda }}\)).

As a result, the set produced by this automaton is recognised by the regular grammar built from the finite-state automaton. This, however, also suggests that the set is regular.

Hence, the statement is proved as true.