Quiz 6                                                                    ROLL NO:____________________

 

CS 311 'Automata & Complexity Theory'                                             Monday, June 24, 2002

Time: 10 min.                                                                                    Total marks: 10

      Open Book / Open Notes

 

Design an NPDA for:

                                                                                                                                      

 

Possible Solution:

 

M = (Q, S, G, d, q0, z, F)

 

Q = {q0, q1, q2, q3, qf}

S = {a, b, c}

G = {1, z}

q0 is the initial state of the control unit

z is the stack start symbol

F = {qf}

Transition function can be defined as:

 

d(q0, a, z) = {q1, 1z}

d(q1, a, 1) = {q2, 1}

d(q2, b, 1) = {q2, 11}

d(q2, c, 1) = {q3, l}

d(q3, c, 1) = {q3, l}

d(q3, l, z) = {qf, l}