# Catenation of Regular Grammars

## Algorithm

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

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

## Example

Give a regular language recognising the catenation of the languages recognised by the following two grammars:

 S aA | bB S aA | bS A aA | a A a B bB | b | where S is the start symbol where S is the start symbol

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 G1 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 A a in G', we replace it with the rule A aS2:

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

where S1 is the start symbol

4. Now we copy all the rules from G2 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 G1, 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