• California State University, San Marcos

• CS 421

CS421 - Krell – HW3C (based on Week 11 and week12a) -- PDA

=================================================================

DUE: Week 12 Friday April 17, before midnight (11:55)

TOTAL: 30 pts

unknown

===================================================================

-------------------------------------------------------

PDA Problem [2pts per problem = 26 pts]

----------------------------------------------------------

1) The language is { (a | b)^n c (a | b)^n | n>=1 }

abab c baba

aaaa c bbbb

Note that the left side and the right side of c need not be

identical. But the lengths of the left and the right side

must be the same.

Start in q0 with Z on the stack. (assumed)

a) Idea: Stay in q0 up to c,

pushing X for a and b as they are read.

Give the 4 Trs's here for all such valid cases:

Trs(q0, a, Z) = (q0, XZ)

Trs(q0,b,Z) = (q0, XZ)

Trs(q0,b,X) = (q0, XX)

Trs(q0,a, X) = (q0, XX)

b) Idea: If c is seen switch to q1. No change to the stack.

Give the Trs here (hint? What is on the stack?):

Trs(q0, a, X) = (q1, X)

c) Idea: In q1, as a's and b's are read, pop off X's.

Give the 2 Trs's here for all such valid cases:

Trs(q1, a , X) = (q1, epsilon)

Trs(q1, b, X) = (q1, epsilon)

The above Trs’s are not enough. We can finish in two different ways as you see below.