Let M be a deterministic PDA with the transition function d:
d(q0,a,Z)= (q1,Z)
d(q1,a,Z)= (q2,Z)
d(q2,b,Z)= (q2,BZ)
d(q2,b,B)= (q2,BB)
d(q2,c,B)= (q3,e)
d(q3,c,B)= (q3,e)
d(q3,c,Z)= (q4,Z)
d(q4,c,Z)= (q4,Z)
Z is the bottom of the stack symbol and e denotes the empty string.
(i) Formally define M by listing all its elements using the definition of d and the assumption that: q0 is the start state and q4 is the only final state of M.
(ii) What is L(M)?
(iii) Show that aabbccc is in L(M) by tracing the computation of M on this input described in terms of configurations and the relation "|-".
My Approach:
i)
M = $<Q,Σ,Γ, q_0, Z, d, F>$
Q = {$q_0$, …, $q_4$}
Σ = {a,b,c}
Γ = {Z}
$q_0$ – start state
Z – stack symbol
F = {$q_4$}
ii) The PDA M accepts strings that have abc as a substring (not sure)
iii)
($q_0$, $a^2b^2c^3$, Z) |- ($q_1$, $ab^2c^3$, Z) |- ($q_2$, $b^2c^3$, Z)
|- ($q_2$, $bc^3$, BZ) |- ($q_2$, $c^3$, $B^2$Z) |- ($q_3$, $c^2$, $B^2$Z)
|- ($q_3$, c, $B^2$Z) |- ($q_4$, e, $B^2$Z) |- accepts since in $q_4$
I believe I did something wrong with B or kept repeating B in every trace…
Best Answer
You can be pretty sure that your answer to (ii) is wrong, since (iii) asks you to show that $aabbccc\in L(M)$, and $aabbccc$ doesn’t satisfy the condition in your answer to (ii).
Notice that there is only one possible transition from the initial state $q_0$, so any word that is accepted must start with $a$. When that $a$ is read, the stack remains empty, but $M$ moves to state $q_1$. Again there is only one transition available, so the next character must also be an $a$ if the word is to have any hope of being accepted. After that second $a$ is read, $M$ is in state $q_2$, and the stack is still empty.
The transitions $d(q_2,b,Z)=(q_2,BZ)$ and $d(q_2,b,B)=(q_2,BB)$ allow $M$ to read $n$ $b$s and place $n$ $B$s on the stack, remaining in state $q_2$ the whole time. Eventually, however, we need an input of $c$ to get out of $q_2$, but since there is no transition for an input of $c$ to state $q_2$ when the stack is empty, we do need to have read in at least one $b$ first. Reading a $c$ pops one $B$ off the stack, and $M$ goes to state $q_3$.
In state $q_3$ all we can do is read $c$s, popping a $B$ off the stack each time, until the stack is empty, at which point the transition $d(q_3,c,Z)=(q_4,Z)$ allows us to read one more $c$ and move to state $q_4$ with the stack empty. The last line of the transition table allows us to read any number of $c$s now, staying in state $q_4$ with the stack empty.
Putting the pieces together, we see that
$$L(M)=\{a^2b^nc^m:n\ge 1\text{ and }m>n\}\;,$$
the set of words that begin with two $a$s, which are followed by any positive number of $b$s, which are followed by more $c$s than there are $b$s.
Your trace of the computation with input $aabbccc$ started out okay, but you should have
$$(q_2,c^3,B^2Z)\vdash(q_3,c^2,BZ)\vdash(q_3,c,Z)\vdash(q_4,\epsilon,Z)\;;$$
each $c$ except the last one pops a $B$ off the stack.