For the pushdown automaton M = (K, , , , s, F ) where K = {s,f}, = {a,b}, = {a,b
ID: 3807188 • Letter: F
Question
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.
Explanation / Answer
There are three possible computations of M on aba:
(s, aba, ) |- (s, ba, a) |- (s, a, aa) |- (s, , aaa)
(s, aba, ) |- (s, ba, a) |- (s, a, aa) |- (f, , aa)
(s, aba, ) |- (f, ba, )
None of these is an accepting configuration.
(b) This is done by tracing the computation of M on each of the strings, as shown in (a).
(c) L(M) is the set of strings whose middle symbol is a. In other words,
L(M) = {xay {a, b}* : |x| = |y|}.