Making a Regular Grammar Epsilon-Free

Algorithm

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.

1. copy all non -productions from G to G'. Let S be the start symbol in G';
2. for any non-terminal N which can become (N is a production), we copy every rule in which N appears on the right hand side both with and without N;
3. if S was in the original set of rules, add a new start symbol S1 in G', add the rule S1 and copy all the production rules with S on the left hand side to ones with S' on the left hand side.

Example

Give an equivalent -free regular grammar to:

where S is the start symbol.

1. copy all -free productions

   S		aA | bB
   A		aA | a
   B		bB | b

   where S is the start symbol.

2. if N is in G, copy every rule in which N appears on the right hand side both with and without N

   S		aA | bB | a | b
   A		aA | a
   B		bB | b

   where S is the start symbol.

3. Since S was a production in the original grammar, add S1

   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.

Exercises

Construct -free regular grammars equivalent to the following regular grammars:

1. G = <	{ a, b, c },
   	{ S, A, B, C },
   	{ S aA | bC, A aA | bB | , B bB | b | , C cB | cC | },
   	S >

2. G = <	{ a, b, c },
   	{ S, A, B, C },
   	{ S aA | bC | , A aA | aS, B b, C cB | cS },
   	S >

3. G = <	{ a, b },
   	{ S, A },
   	{ S aA | bS, A },
   	S >

4. G = <	{ a },
   	{ S },
   	{ S},
   	S >