theoryautomatacomputation
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 ....
Solution
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:
