Removing the Empty String from a Language

Algorithm

For a regular grammar G, we construct a regular grammar G' such that L(G') = L(G) \ {}:

  1. make G -free. Call the new grammar constructed by G';
  2. if present, remove the rule S' from the productions of G', where S' is the start symbol in 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.

Example

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.

  1. Make the grammar -free:

    < /TR>
    S1 aA | bB | a | b |
    S aA | bB | a | b
    A aA | a
    B bB | b

    where S1 is the start symbol.

  2. Remove 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 except that they do not recognise :

  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 >