CODEWITHSUNDEEP
automataformal-languagespushdown-automaton
kepler
kepler

Reputation: 31

PDA to accept language with more a's than b's and c's

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.

Upvotes: 3

Views: 1957

Answers (1)

Patrick87
Patrick87

Reputation: 28312

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.

Upvotes: 2

Related Questions