Recall that a regular grammar is said to be -free if it has no -productions except possibly for the production S, where S is the start symbol, and does not appear on the right hand side of the production rules.
Give an equivalent -free regular grammar to:
S | aA | bB | | |
A | aA | a | | |
B | bB | b | |
where S is the start symbol.
S | aA | bB | |
A | aA | a | |
B | bB | b |
where S is the start symbol.
S | aA | bB | a | b | |
A | aA | a | |
B | bB | b |
where S is the start symbol.
S1 | ||
S | aA | bB | a | b | |
A | aA | a | |
B | bB | b |
where S1 is the start symbol.
... and copy all rules from S to S1
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:
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 > |