# Understanding PDA for odd length string with middle symbol 0

I came across this pdf, which describes the language of odd length string with middle symbol 0 as follows: 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?

Posted on Categories proxies