Kleene Star Closure of Finite State Automata

Algorithm

Given a finite state automaton M, this transformation constructs another FSA M' which recognises the kleene star of the language. That is, L(M') = (L(M))^*.

1. construct a regular grammar G from M (see the relevant algorithm);
2. apply the kleene star closure transformation for regular grammars to G to get regular grammar G' (see the relevant algorithm);
3. construct an FSA M' from G' (see the relevant algorithm)

Example

Consider the following FSA:

1. We start by constructing an equivalent regular grammar:

   S		a | aA
   A		aB | bB
   S		b | bA

   where S is the start symbol.

2. We use the appropriate algorithm to obtain a regular grammar which recognises the Kleene star closure of the language recognised by the above grammar:

   S1		a | aA | aS |
   S		a | aA | aS
   A		a | bB
   B		b | bA | bS

3. Finally, we construct a FSA M' equivalent to the above grammar:

   

Exercises

Construct FSA which recognise the Kleene star closure of the following languages described using FSA: