CODEWITHSUNDEEP
theoryautomatacomputation
user1078020
user1078020

Reputation: 15

Push Down Automata

designing a pushdown automata for the language a^n b c^n+2, n>0 I have been asked to implement the automata for the above language .. please help?

I tried popping a 2 (c)s everytime I push an (a) on to the stack but it seems not to work with odd number of (a)s ....

Upvotes: 0

Views: 895

Answers (1)

franvergara66
franvergara66

Reputation: 10784

You must process the a's in the normal way, ie, for each to read from the tape you stack A, until you finish reading the a's, if you read a b, leave the top of the stack as it is, finally you must process all C's. The transition function is:

(q0, a, Z) = (q0, AZ)
(q0, a, A) = (q0, AA)
(q0, b, A) = (q1, A)
(q1, c, A) = (q1, epsilon) (until the amount of a's are equal to the amount of c's)
(q1, c, Z)= (q2, Z) (read the first extra c)
(q2, c, Z)= (q3, Z) (read the second extra c)
(q3, epsilon, Z)= (qf, Z) (qf is the final state)

The graphic representation of the PDA is:

enter image description here

Upvotes: 2

Related Questions