Autometa | PDA

Question

Consider the following Language:

L= $a^{n}b^{n}c^{n}$ | $n \geq 0$

Consider the following Statement:

• A PDA can accept the given language. As we can insert 2 a’s for every entry of a, and pop one ‘a’ for every b and after all b’s, pop one ‘a’ for every entry of ‘c’

So the above language is a CFL.

Prove the above statement WRONG

Comments

$a^{n}b^{n-k}c^{n+k}$ will be also accepted by the pda which should not be .

---

two stacks required here.

---

$a^nc^nb^n$ is also accepted, but what is the counter for that logic?

---

More than 2 Infinite non linear power comparisons can’t be done by PDA. 

@Kabir5454 ‘s logic is correct. 

Answer 1

The logic given is for the Language a^n b^m c^k where m+k = 2n. This can be done using a single stack. And a^n b^n c^n is a subset of this Language. Now we can say a Language is accepted by a PDA when the PDA accepts all the strings generated by the Language and rejects strings which are not part of the Language set. The logic which you are talking about will surely accept all the strings of type a^n b^n c^n but it can also accept strings like “aabbbc” which should have been rejected. So that is why we can’t say that it is a CFL.