# Kleene Star Closure of Regular Grammars

## Algorithm

Given regular grammar G, we would like to construct a regular grammar G' such that L(G') = (L(G))*:

1. construct the kleene plus of the regular grammar (see the relevant section);
2. add to the language (see the relevant section)

## Example

Give a regular grammar recognising the Kleene star closure of the language recognised by the following grammar:

 S aA | bB A aA | a B c | bS

where S is the start symbol.

1. Construct the Kleene plus closure of the language:

 S aA | bB A a | aA | aS B c | cS | bS

where S is the start symbol.

2. Add to the language:

 S1  | aA | bB S aA | bB A a | aA | aS B c | cS | bS

where S1 is the start symbol.

## Exercises

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

1. G = < { a, b, c },
{ S, A, B, C },
 { S aA | bC, A aA | bB | , B bB | b | , C cB | cC | },
S >
2. G = < { a, b, c },
{ S, A, B, C },
 { S aA | bC | , A aA | aS, B b, C cB | cS },
S >
3. G = < { a, b, c },
{ S, A, B, C },
 { S aA | bC | , A aA | aS, B b, C cB | cS },
S >
4. G = < { a, b },
{ S, A },
 { S aA | bS, A  },
S >
5.  G = < { a }, { S }, { S  }, S >