# 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 A a (A being a non-terminal and a a single terminal), we add the rule A aS, 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:

 S aA | bB A aA | a | B c | bS | 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 A a (A being a non-terminal and a a single terminal), we add the rule A aS:

 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 >