Question: For the pushdown automaton M = (K, , , , s, F ) where K = {s,f}, = {a,b}, = {a,b}, F = {f}, and

For the pushdown automaton M = (K, , , , s, F ) where K = {s,f}, = {a,b}, = {a,b}, F = {f}, and consists of the following transitions:

((s, a, e), (s, aa)), ((s, b, e), (s, b)), ((s, e, e), (f, e)), ((f, a, a), (f, e)), ((f, b, b), (f, e))

out of the strings in L(M): aaa, bbbb, abbaabb, aabbbb, abaaabaa, abaaba, aabba

I got that aaa, bbbb, abaaabaa are the only ones that work, is this correct?

I also need to describe the language in simpler terms without reference to the push down automaton. from the 3 I have it seems that the strings are being reversed and the a's are being doubled but I don't know how to express that in terms of w. I tried xwx^2 = wE {a,b}* & xE {a}* but this doesn't work out.

Step by Step Solution

There are 3 Steps involved in it

1 Expert Approved Answer
Step: 1 Unlock blur-text-image
Question Has Been Solved by an Expert!

Get step-by-step solutions from verified subject matter experts

Step: 2 Unlock
Step: 3 Unlock

Students Have Also Explored These Related Databases Questions!