What is Kleene's theorem?

Kleene's theorem is used to show the equivalence between regular languages, regular expressions, and finite automata. Kleene's theorem states that:

For any regular expression of a language, there exists a finite automaton.

In simple words, a regular expression can be used to represent a finite automaton and vice versa. Regular expressions are composed of unions, concatenations, and Kleene's starKleene's star is unary operation in which the character or expression is repeated n number of times..

Kleene's theorem defines rules to perform these operations on regular expressions to convert them into finite automata.

Conversion of regular expressions to FA's

Rules

The following rules are followed to make conversions:

• For union operations, a new initial state is introduced and is connected to the individual FA's that are to be unionized.

 For example, $M_1+M_2$, where $M_1$ and $M_2$ can be any regular expression.

• For concatenation operations, a FA is connected to the other by making null transitions from the final state(s) of the first FA to the initial state of the second FA.

  For example, $M_1.M_2$, where$M_1$and $M_2$are two FA's of a regular expression.

  After performing concatenation, the FA will look as follows:

• For Kleene's star operations, the final state of the FA is looped back with a null transition to a new initial state that is introduced.

  For example, $(M_1)^*$where$M_1$can be any regular expression

Example

Let's see an example:

Suppose a regular expression $ab+b^*$. The FA's mentioned below are the building block of the complete regular expression.

In the next step, the FA's above are used to construct $ab \space and\space b^*$.

By applying union to the FA's above, the resultant FA is as follows:

To see the generation of FA's to regular expressions by the state elimination method, click here