Kleene Plus 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. remove from the language described by G (see the relevant section), thereby removing all -productions from the grammar;
2. for every rule in the form Aa (A being a non-terminal and a a single terminal), we add the rule AaS, where S is the start symbol of G;
3. if S was originally in the productions of G, we add to the language generated by the grammar (see the relevant section)

Example

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

where S is the start symbol.

1. Remove from the language:

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

   where S is the start symbol.

   Note that was not in the language, but the procedure removes the undesirable -productions in the grammar.

2. For every rule in the form Aa (A being a non-terminal and a a single terminal), we add the rule AaS:

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

   where S is the start symbol.

3. Since the language did not contain the empty string (since S was not in the grammar), we are done.

Exercises

Construct regular grammars which recognise the Kleene plus 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 >