Theory of Computation #4

Exercise 1.5.2: Show that the grammar below can be modified to be a regular grammar without changing the language it generates.

S -> xyX
X -> xxX
X -> yY
Y -> lambda (empty string)

Let’s think about the rules of regular grammars:

• left side has to be a single nonterminal
• the right side must be
• a) a terminal followed by a nonterminal
• b) a single terminal
• c) the empty string (lambda)

The first rule is already fulfilled. Therefore, we only have to take care of the second one. The problems are the first and second line of our grammar which contains two terminals and a nonterminal. The last two lines aren’t affected by any changes we will do.

S -> xyX
X -> xxX

Start with the start state S. We can transform it like this:

S -> xA
A -> yX

And the second state X can be transformed like this:

X -> xB
B -> xX

Why can’t we just write X -> xX? The answer is that we have two rules for X. If we would just write xX the output could be x(yY) which isn’t equal to xxX.

So our new grammar is:

S -> xA
A -> yX
X -> xB
B -> xX
x -> yY
y -> lambda.

Exercise 1.5.3: Convert the regular grammar below to another regular grammar that contains no rewrite rules whose right sides consist of a single terminal, and yet generates the same language. Describe the language generated in your own words.

S -> xS
S -> y
S -> z

This is an interesting grammar. Let’s take a look at some derivations.

y
z
xy
xz
xxy
xxz
xxxy
xxxz
...

Now take a look back at the definition of a regular grammar. We need some way to end the string and we will use lambda. I hope I understand the definition correctly in this case that this isn’t considered a single terminal. Therefore we need some state like A -> lambda.

S -> xS
S -> yA
S -> zA
A -> lambda

And this should do the job.