Does this language have a Pushdown Automata ( PDA )?

Question

the language is: { Aⁿ B⁽²ⁿ⁾ Cⁿ | where n>=0 }

I think it has, because you can process it like this: push A's, push B's, for each C pop three times from stack, if there are no C's and stack is empty, return true, else return false.

Answer 1

Use the pumping lemma to prove this is not a context-free language.

Consider s = a^p b^2p c^p
Then we consider vxy, |vxy|<=p, |vy|>0 and uvⁱxyⁱz in L
We have the possibilities

1. vxy = a^j, j<=p
2. vxy = a^j b^k, j+k<=p
3. vxy = b^j, j<=p
4. vxy = b^j c^k, j+k<=p
5. vxy = c^j, j <=p

In any case, there are no constants u and v s.t. the string is in L, because there can only be two symbols in vxy and we would then need a variable amount of the third to show in up u or v

Your proposed automata fails on AAAC, returning true. It doesn't guarantee that you have twice as many B's as A's.

Answer 2

No such PDA exists because this language is not context-free. Here's a short proof of this. This relies on the fact that context-free languages are closed under inverse homomorphism (as mentioned in these slides).

Given the language L = { AⁿB²ⁿCⁿ | n in N }, consider the homomorphism h defined from

• h(A) = A
• h(B) = BB
• h(C) = C

The inverse of this homomorphism, as applied to L, is the language h^-1(L) = { x in Σ* | h(x) ∈ L }. Looking over the choice of h, this is the language { AⁿBⁿCⁿ | n in N }. This language is a canonical example of a non-context-free language. Howver, the CFLs are closed under inverse homomorphism, so because h^-1(L) is not context-free, L cannot be context-free. Therefore, there is no PDA for it.

Hope this helps!