Union of Regular Grammars

Algorithm

Given two regular grammar G₁ and G₂, we want to construct a regular grammar G such that L(G) = L(G₁) U L(G₂):

1. rename the non-terminals of G₁ and G₂, such that they have no common non-terminals. One possible way is to add 1 to all the non-terminals in G₁, 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₁ and G₂ respectively);
3. copy all production rules in G₁ and G₂ to G

Example

Give a regular grammar recognising the union of the languages described by the following grammars:

1. Rename the non-terminals:

   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

2. 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₁ and G₂ with S1 or S2 on the left hand side:

   S

   aA1 | bB1 | aA2 | bS2

   where S is the start symbol

3. Copy all the rules in G₁ and G₂ 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):

1. 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

2. 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

3. 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

4. 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