[Math] Pushdown Automata formal definition, L(M), tracing input

automataformal-languages

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.

Related Question