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):
- 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;
- if is in L1, modify G1 so as to
remove it (hence obtaining an -free grammar);
- for every rule in G1 of the form Aa,
we replace it with the rule AaS2, where S2 is
the start symbol of G2.
- copy all the production from G2 to
G1;
- 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 |
- 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 |
- Remove from G1 to obtain G:
S1 | |
aA1 | bB1 | b |
A1 | | aA1 | a |
B1 | | bB1 | b |
where S1 is the start symbol
- 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
- 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
- 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):
-
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 |