Adding the Empty String to a Language
Algorithm
- Add the production S' (S' being a new
non-terminal).
- 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.
- 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.
- Add S'.
S | | aA | bB |
A | | aA | a |
B | | bB | b |
S' | | |
- 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 |
- Set S' to be the new start symbol.
Exercises
Add the empty string to the languages accepted by the following
regular grammars:
-
G = < | { a, b }, |
| { S, A, B }, |
|
{ | S | |
aA | bB, |
| A | |
aA | a, |
| B | |
b | bB | bS }, |
|
| S > |
-
G = < | { a, b }, |
| { S, A, B }, |
|
{ | S | |
aA | bB | , |
| A | |
aA | a, |
| B | |
b | bB | bS }, |
|
| S > |
-
G = < | { a, b }, |
| { S, A }, |
| |
| S > |
-
G = < | { a }, |
| { S }, |
| {
S},
|
| S > |