0
$\begingroup$

I came across this pdf, which describes the language of odd length string with middle symbol 0 as follows:

enter image description here

Doubts:

  1. I dont understand the transition labels. In standard resources like books by Ullman et al, Linz and in wikipedia, the transition labels take following form:

    • $a,b/ab$ means if next input symbol is $a$ and current stack top is $b$, then push $a$ on $b$
    • $a,b/\epsilon$ means if next input symbol is $a$ and current stack top is $b$, then pop $b$
    • $a,b/a$ means if next input symbol is $a$ and current stack top is $b$, then pop $b$ and push $a$

    I dont get meaning of transition labels in diagram $a,b\rightarrow c$. Some one explained me that its, if next next input symbol is $a$, pop $b$ and push $c$. I feel, if this interpretation is correct, then this notation is insufficient as it will describe both $a,b/ab$ and $a,c/ac$ as $a,\epsilon\rightarrow a$. Am I right with this, or I understood the notation incorrectly?

  2. Assuming above interpretation to be correct, loop on $q_1$ pushes all input symbols, be it 1 or 0. Then for $0$ at any position (not necessarily middle position), it transits to $q_2$. Loop at $q_2$ pops all symbols. I dont get how above PDA forces middle symbol to be $0$. Also I dont get how it ensures length of $w$ is odd.

  3. If given PDA is incorrect, can we prepare correct one by re-labelling as follows:

    • Loop at $q_0$: $\{(1,\$/1);(0,\$/1);(0,0/00);(0,1/01);(1,0/10);(0,1/01)\}$
    • Transition $q_0-q_1$: $\{(0,0/0);(0,1/1)\}$
    • Loop at $q_2$: $\{(0,0/\epsilon);(0,1/\epsilon);(1,0/\epsilon);(1,1/\epsilon)\}$

    So, its CFL not deterministic CFL, right?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.