Catenation of Regular Grammars

Algorithm

For two regular grammar G₁ and G₂, we construct a regular grammar G such that L(G) = L(G₁) L(G₂):

1. rename the non-terminals of G₁ and G₂, so as to have disjoint non-terminal sets. One possible way is to add 1 to the end all the non-terminals in G₁, and 2 to those in G₂;
2. if is in L₁, modify G₁ so as to remove it (hence obtaining an -free grammar);
3. for every rule in G₁ of the form Aa, we replace it with the rule AaS2, where S2 is the start symbol of G₂.
4. copy all the production from G₂ to G₁;
5. if was in L₁, add the rule S1, where S1 is the start symbol in G₁.

Example

Give a regular language recognising the catenation of the languages recognised by the following two 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. Remove from G₁ to obtain G:

   S1		aA1 | bB1 | b
   A1		aA1 | a
   B1		bB1 | b

   where S1 is the start symbol

3. For every rule of the form Aa in G', we replace it with the rule AaS2:

   S1		aA1 | bB1 | bS2
   A1		aA1 | aS2
   B1		bB1 | bS2

   where S1 is the start symbol

4. Now we copy all the rules from G₂ to G':

   S1		aA1 | bB1 | bS2
   A1		aA1 | aS2
   B1		bB1 | bS2
   S2		aA2 | bS2
   A2		a

   where S1 is the start symbol

5. Since S1 was in the language of G₁, we add to the language recognised by G':

   S		aA1 | bB1 | bS2 |
   S1		aA1 | bB1 | bS2
   A1		aA1 | aS2
   B1		bB1 | bS2
   S2		aA2 | bS2
   A2		a

   where S is the start symbol

Exercises

Construct a regular grammar that recognises the catenation 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