Adding the Empty String to a Language

Algorithm

  1. Add the production S' (S' being a new non-terminal).
  2. Copy all productions with S (the start symbol) on the left hand side to the similar production but with S' on the right hand side.
  3. Set S' to be the new start symbol.

Example

Give a regular grammar recognising the language recognised by the following regular grammar together with .

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

where S is the start symbol.

  1. Add S'.

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

  2. Copy all productions with S (the start symbol) on the left hand side to the similar production but with S' on the right hand side.

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

  3. Set S' to be the new start symbol.

Exercises

Add the empty string to the languages accepted by the following regular grammars:

  1. G = < { a, b },
    { S, A, B },
    {S aA | bB,
    A aA | a,
    B b | bB | bS },
    S >
  2. G = < { a, b },
    { S, A, B },
    {S aA | bB | ,
    A aA | a,
    B b | bB | bS },
    S >
  3. G = < { a, b },
    { S, A },
    {S aA,
    A b | },
    S >
  4. G = < { a },
    { S },
    { S},
    S >