Kleene Plus Closure of Finite State Automata

Algorithm

Given a finite state automaton M, this transformation constructs another FSA M' which recognises the kleene plus 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 plus 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		aS | bB
   B		b | bA

   where S is the start symbol.

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

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

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

   

Exercises

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