how to construct pda for a^i b^j where j!=2i+1, i>=0

Question

how to construct pda for a^i b^j where j!=2i+1, i>=0 ?

i have constructed for j=2i+1 but by complementing the states do we get actual n pda of our requirement?

whether it is decidable?

Answer 1

Construct for j>2i+1 and j<2i+1 then take the union of these two pda that will be j!=2i+1.

Comments

Nopes. A complement language must include every string in $\Sigma^*$ not in $L$. Here, "ba" should be in $L'$.

---

I guess here we have to design for L not the complement of L and yes off course CFL language is not closed under complement so we cant design for complement of a CFL language it would be CSL.

Here L is a CFL so npda exist , yes "ba" should be in L' not in L(coz it is a^ib^j) and we are designing for L i think which means "ab" should exist and we design using union it will exist in npda. (please let me know if i am incorrect.)

Ll

Answer 2

Yes, but works for only deterministic PDAs and has problems and won't work straight away- see below link.

http://drona.csa.iisc.ernet.in/~deepakd/atc-2011/DPDA.pdf

For NPDA, a complement PDA may not even exist.