PDA that accepts L $\{a^i b^j c^k \mid i,j,k≥0 \text{ and } i=j \text{ or } i=k\}$

Question

I have to construct a PDA which accepts the L $\{a^i b^j c^k\mid i,j,k ≥ 0 \text{ and } i=j \text{ or } i=k\}$

I have been at it for hours but whenever I try to design one, it fails the test.

The string from the L is something like this $\{c,b,ab,ac,abcc,abbc,aabb,aabbccc,aabcc,\ldots\}$ because the amount of a's is either the same as the b's or the c's, never at the same time.

I came up with the following PDA, but it says that the strings fail. Can someone please help me out?

I've been doing this for a good five hours so a hint would really be appreciated. Thank you.

Final states:S2, S3, S6

Answer 1

You can make a PDA for the simpler language $\{a^ib^jc^k \;|\; j=k\}$ as follows.

• At the beginning, it pushes $A$ onto the stack.
• Whenever it reads input $a$, as long as $A$ was just popped off the top of the stack, it pushes $A$ back onto the stack.
• Whenever it reads input $b$, as long as $A$ or $B$ was just popped off the top of the stack, it pushes that symbol back on with another copy of $B$ on top.
• Whenever it reads input $c$, as long as $B$ was just popped off the top of the stack, it continues without pushing anything onto the stack.
• Whenever the automaton reads a symbol and the stack state doesn't match any of the given rules, it rejects the string.

You can make a similar PDA for the language $\{a^ib^jc^k \;|\; i=j\}$. Suppose for this machine, you use the symbols $A^\prime, B^\prime, C^\prime$ in place of $A, B, C$.

Then to make a PDA that recognizes the union of these two languages as required, define a PDA that has all of the transition rules for both machines, except in the first stage, it nondeterministically puts either $A$ or $A^\prime$ on top of the stack. Then this machine will start by nondeterministically guessing whether the word has $i=j$ or $j=k$, then follow the rules of the corresponding PDA. If either branch is a correct guess, the machine will accept. Hence the machine accepts your language as required.