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))^{+}:
 remove from the language described by G (see the
relevant section), thereby removing
all productions from the grammar;
 for every rule in the form Aa (A being a nonterminal
and a a single terminal), we add the rule
AaS, where S is the start symbol of G;
 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.
 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.
 For every rule in the form Aa (A being a nonterminal
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.
 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:

G = <  { a, b, c }, 
 { S, A, B, C }, 

{ 
S 

aA  bC, 

A 

aA  bB 
, 

B 

bB  b 
, 

C 

cB  cC 
}, 

 S > 

G = <  { a, b, c }, 
 { S, A, B, C }, 

{ 
S 

aA  bC 
, 

A 

aA  aS, 

B 

b, 

C 

cB  cS }, 

 S > 

G = <  { a, b, c }, 
 { S, A, B, C }, 

{ 
S 

aA  bC 
, 

A 

aA  aS, 

B 

b, 

C 

cB  cS }, 

 S > 

G = <  { a, b }, 
 { S, A }, 
 
 S > 

G = <  { a }, 
 { S }, 
 { S},

 S > 