For a regular grammar G, we construct a regular grammar G' such that L(G') = L(G) \ {}:
Refer to the appropriate section to see more details about step 1.
Note that this procedure is guaranteed to leave a grammar with no -productions. It will thus be used elsewhere in other transformations which expect an -free grammar to work with.
Give a regular grammar recognising the same language as the following grammar except for the empty string.
S | aA | bB | | |
A | aA | a | | |
B | bB | b | |
where S is the start symbol.
S1 | aA | bB | a | b | | < /TR>|
S | aA | bB | a | b | |
A | aA | a | |
B | bB | b |
where S1 is the start symbol.
S1 | aA | bB | a | b | | |
S | aA | bB | a | b | |
A | aA | a | |
B | bB | b |
where S1 is the start symbol.
Construct -free regular grammars equivalent to the following regular grammars except that they do not recognise :
G = < | { a, b, c }, | ||||||||||||||||
{ S, A, B, C }, | |||||||||||||||||
| |||||||||||||||||
S > |
G = < | { a, b, c }, | ||||||||||||||||
{ S, A, B, C }, | |||||||||||||||||
| |||||||||||||||||
S > |
G = < | { a, b }, | ||||||||
{ S, A }, | |||||||||
| |||||||||
S > |
G = < | { a }, |
{ S }, | |
{ S}, | |
S > |