3

My question is similar to this one. I was wondering if a PDA exists, that accepts any words containing a's, b's and c's in a random order, where the total amount of a's is higher than the amount of the b's and higher than the amount of c's, so for example the word "abcacba" would be accepted.

kepler
  • 31
  • 2
  • The technique in the link (using the stack as a counter to track the value of *a-b*) won't work, as you'd need to track *a - max(b,c)*, but I also don't see a good way of applying the pumping lemma to show that it is impossible. – Chris Dodd Oct 10 '18 at 16:30
  • Might be better on https://cs.stackexchange.com/ ? – Chris Dodd Oct 10 '18 at 16:35
  • Yeah, I also thought about applying the pumping lemma, but had no idea, too. And you're right, I'll ask the question on Stackexchange as well, thanks for the hint. – kepler Oct 10 '18 at 16:47
  • @kepler: instead, not as well. Please delete the question here; questions should normally be directed to only one site. – rici Oct 10 '18 at 19:25
  • @kepler As mentioned by others, please avoid cross posting. I suggest trying your questions on CS both here and at cs.stackexchange.com and making up your own mind about where you get better answers faster. Please consider my response to burnabyRails's comment before deciding to delete the question here. HenrikJan and the others as CS know their stuff but convincing them to just answer the question can be a real chore sometimes, or at least that's my experience. – Patrick87 Oct 15 '18 at 16:01

1 Answers1

2

This is not a context-free language. The proof is by the pumping lemma for context-free languages. Assume the language is context-free. Then every string in the language of length greater than p can be rewritten as uvxyz such that |vxy| < p, |vy| > 0 and for every natural number k, u(v^k)x(y^k)z is also a string in the language. Now, consider the string [a^(p+1)][b^p][c^p]. There are several ways to write this as uvxyz. Let us consider all possible cases for the substring vxy:

  1. the pumpable part of vxy consists only of a's. Pumping up works, but k = 0 is a valid choice and pumping down fails since pumping down will decrease the number of a's by at least one.
  2. the pumpable part of vxy consists of a's and b's: pumping down will decrease the a's without decreasing the c's, violating the requirement.
  3. the pumpable part of vxy consists only of b's: pumping up will increase the number of b's above the fixed number of a's, violating the requirement.
  4. the pumpable part of vxy consists of b's and c's: pumping up will increase the number of b's and c's without changing the number of a's, violating the requirement.
  5. the pumpable part of vxy consists only of c's: pumping up will increase the number of c's without changing the number of a's, violating the requirement.

Therefore, there is no way to write our word as uvxyz while satisfying the requirements of the pumping lemma, a contradiction. Our assumption that the language is context free is therefore refuted.

Patrick87
  • 27,682
  • 3
  • 38
  • 73
  • @burnabyRails What happens if you pump *down*, that is, `u(v^0)x(y^0)z`? The pumping lemma requires this, too. It seems to me that in your example, you'd get the string `a^p b^p c^p` which is not a string in `L`. – Patrick87 Oct 15 '18 at 15:47