I am a bit confused on how to give a formal definition of the language accepted by A? PDA

I can describe it by "The language of all strings starting with n-many a's or n-many c's followed by n-many b's" and I have tried to give a formal definition by:

L(A) = {a^n c^n b^n | n ∈ N}

Is that the correct way to define it?

  • $\begingroup$ The language $\{a^nc^nb^n \mid n \in \mathbb{N}\}$ is not context-free, so this can't be it. $\endgroup$ May 10 '20 at 6:35

I would say it's $L(A)=\{a^n c^m b^{2n}| n,m \in \mathbb{N}, m \geq 2\}$

For every a push 2 zeros on the stack, so it's for now just called a^n. The number of c's is m, because it is not related to the number of a's. You can accept any number of c's (larger than 2) no matter how many a's were there. The number of b's is twice the number of a's because you accept for every 0 on the stack 1 b, but wrote twice 0 for every a on the stack.

In fact the language $L(A)=\{a^n c^n b^n| n \in \mathbb{N}\}$ can't be accepted by any PDA, but only a linear bounded automate(LBA) or a Turingmachine (or other similar models) The reasoning is that if you count the number of a's and want to have the same number of c's and b's later(not mixed) your stack will be empty after you sucessfully counted all the c's and the PDA will have forgotten the number to check whether the b's appear in this number.

  • $\begingroup$ The number of c's is greater than or equal to 2. $\endgroup$ May 9 '20 at 19:35
  • $\begingroup$ @JimHefferon Thank you. I missed that first. I edited it now $\endgroup$
    – jt0202
    May 9 '20 at 20:58
  • $\begingroup$ Oh, thank you both very very much $\endgroup$
    – Yani
    May 9 '20 at 21:04

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.