Union of Regular Grammars
Algorithm
Given two regular grammar G_{1} and G_{2},
we want to construct a regular grammar G such that
L(G) = L(G_{1}) U L(G_{2}):
 rename the nonterminals of G_{1} and G_{2},
such that they have no common nonterminals. One possible way is
to add 1 to all the nonterminals in G_{1}, and
2 to those in G_{2}.
 in the regular grammar G add start symbol S and copy all
rules with S1 or S2 on the left hand side to ones with S
(where S1 and S2 are the start symbols in
G_{1} and G_{2} respectively);
 copy all production rules in G_{1} and
G_{2} to G
Example
Give a regular grammar recognising the union of the languages
described by the following grammars:
S  
aA  bB 

S  
aA  bS 
A  
aA  a  \e 

A  
a  
B  
bB  b  

  
where S is the start symbol 

where S is the start symbol 
 Rename the nonterminals:
S1  
aA1  bB1 

S2  
aA2  bS2 
A1  
aA1  a  

A2  
a  
B1  
bB1  b  

  
where S1 is the start symbol 

where S2 is the start symbol 
 Create a new grammar G with start symbol S and
rules starting from S and going to the right hand sides of
the rules in G_{1} and G_{2}
with S1 or S2 on the left hand side:
S  
aA1  bB1 
aA2  bS2 
where S is the start symbol
 Copy all the rules in G_{1} and G_{2}
to G:
S  
aA1  bB1 
aA2  bS2 
{S1}   aA1  bB1 
{S2}   aA2  bS2 
{A1}   aA1  a  
{A2}   a  
{B1}   bB1  b  
where S is the start symbol
Exercises
Construct a regular grammar that recognises the union
of the following pairs of languages (described using regular grammars):

S   aA  bC 

S   aA  bS 
A   aA  aB 

A   aS  b 
B   bB  b 

  
C   cB  cC 

  
where S is the start symbol 

where S is the start symbol 

S   aA  bC 

S   aA  bS 
A   aA  aB 

A   a 
B   bB  b 

  
C 
 cB  cC  

  
where S is the start symbol 

where S is the start symbol 

S   aA  bS 

S   aA 
bC  
A   a 

A   aA  aB 
  

B   bB 
b  
  

C   cB  cC 
where S is the start symbol 

where S is the start symbol 

S   aA 
bC  

S   
A   aA  aB 

  
B   bB  b 


  
C   cB  cC 

  
where S is the start symbol 

where S is the start symbol 