in Books, Doing Books, Theory of Computation

Theory of Computation #8

Excercise 2.1.2: What language is accepted by the pushdown automaton whose transition diagram is shown below?


So, we have one state which is also an acceptance state. We also have to transitions. The first one reads x, pops empty string and pushes x. The second one reads y, pops x and pushes empty string.

We can pop empty strings immediately therefore it starts with reading x. As soon as a y is read it we have to pop an x, i.e. we can only read as many ys as xs but we can read as many xs as we want.

Therefore the language is consists of all elements which hold x^n  y^m where m <= n. Some examples: x, xxxy, xxyxyyx, etc.



Exercise 2.3.5: Convert the following grammar, with start symbol S, into grammar in Chomsky normal form that generates the same language.

S -> xSy
S -> wNz
N -> S
N -> lambda.

As a reminder the Chomsky normal form (CNF) can have the following constructs:

A -> BC
A -> a or
S -> lambda

This language doesn’t include the empty string therefore we will only need the first two constructs.

Start with the first rule: S -> xSy. We can transform it to:

S -> XA
A -> SY


X -> x
Y -> y.

The next rule is: S -> wNz. N can either be S or lambda, therefore this rule can be expanded to:

S -> wz and S -> wSz. We can rewrite this in CNF as:

S -> WZ
S -> WB
B -> SZ


W -> w
Z -> z.

Write a Comment


This site uses Akismet to reduce spam. Learn how your comment data is processed.