# Is a Pushdown Automata possible for this language?

PDA for a Language L = { $a^i b^j \mid i \neq 2j+1 \}$ over the Alphabet $\Sigma = \{a,b\}$

If it can be constructed, how?

Edit : I've tried make the PDA for $$L = \{ a^i b^j \mid i = 2j+1 \}$$ (with the intention of editing the PDA to accept if $a$ or $b$ is leftover) but can't figure out how to push the proper number of $a$'s.

• What have you tried? Where did you get stuck? Perhaps start by trying to construct a PDA for $\{a^nb^m:n\neq m\}$. Dec 21 '15 at 8:07
• Note that in general, it is not possible to complement PDAs (since CFL is not closed under complementation). So it is not entirely clear that a PDA for $\{a^ib^j:i=2j+1\}$ would help. But still, it's a possible starting point. Recall that you can push multiple $a$'s without reading anything from the word, as this is allowed in PDAs. e.g. have $\delta(q,\epsilon)=(q',a,\epsilon)$. Dec 21 '15 at 8:33
• Just push one $A$ for every $a$ you have. Then delete the proper number of $A$'s for each $b$. Dec 21 '15 at 8:33
• @Shaull For the $\{a^nb^m:n\neq m\}$ I believe this is a solution. How does this help my problem, though? I can only apply this if I can accept the proper number of $a$'s. Dec 21 '15 at 8:41
• Another possible way to think about it is this: $x \neq y$ implies that either $x <y$ or $x > y$. Dec 21 '15 at 13:01

The construction for PDA will be as follows :

1) Push all $a's$ into stack

2) For every $b$ pop two $a'$ from stack, continue this till all $b$ exhaust there will be three condition for acceptance -

1) If stack got empty before $b$ exhaust

2) If stack got empty and $b$ exhaust

3) If there exist more than one $a$ in stack after $b's$ exhaustion.

else REJECT.