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.

  • 1
    $\begingroup$ What have you tried? Where did you get stuck? Perhaps start by trying to construct a PDA for $\{a^nb^m:n\neq m\}$. $\endgroup$
    – Shaull
    Dec 21 '15 at 8:07
  • $\begingroup$ 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)$. $\endgroup$
    – Shaull
    Dec 21 '15 at 8:33
  • $\begingroup$ Just push one $A$ for every $a$ you have. Then delete the proper number of $A$'s for each $b$. $\endgroup$ Dec 21 '15 at 8:33
  • $\begingroup$ @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. $\endgroup$ Dec 21 '15 at 8:41
  • 3
    $\begingroup$ Another possible way to think about it is this: $x \neq y$ implies that either $x <y$ or $x > y$. $\endgroup$
    – G. Bach
    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.


Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.