2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

Note the language where the number of $a$'s is larger than both the number of $b$'s and the number of $c$'s is not context-free, and cannot be accepted by a PDA.

Formally the language can be written as $L = \{ x\in\{a,b,c\}^*\mid \#_a(x) > \#_b(x) \text{ and }\#_a(x) > \#_c(x) \}$.

Intuitively we cannot recognize $L$ using a single pushdown as the count of $a$'s has to be used twice, but in comparing with the number of $b$'s and the number of $c$'s. That is no formal argument, there might be clever tricks avoiding the direct comparison of numbers. Yet there is a possible water tight proof, it uses the pumping lemma for context-free languages.

$\endgroup$
1
$\begingroup$

Let $L$ be the language of words with more $a$'s than $b$'s and $c$'s. No PDA can accept $L$ since $L$ is not context-free.

This answer is a proof for the non-context-free-ness using pumping lemma that is mentioned in Hendrik Jan's answer.

Assume $L$ is context-free for the sake of contradiction. Then there is a $p\ge1$, the pumping length such that every word in $L$ of length no less than $p$ can be written as $uvxyz$ such that $|vxy| \le p$, $|vy| \ge 1$ and $uv^kxy^kz$ is also a word in $L$ for all nonnegative number $k$.

Consider the word $a^{p+1}b^pc^p$ that is in $L$ but "almost not in $L$". Write it as $uvxyz$ as said above. Call $v$ and $y$ together the pumpable part of the word. Since $vxy$ is too short to contain both $a$ and $c$, there are three cases for the pumpable part.

  • the pumpable part contains at least one $a$. Then it cannot contain $c$. Pumping down by letting $k=0$ will decrease $a$'s without decreasing the $c$'s.
  • the pumpable part contains at least one $c$. Then it cannot contain $a$. Pumping up by letting $k=2$ will increase $c$'s without increasing the $a$'s.
  • the pumpable part contains $b$ only. Pumping up by letting $k=1$ will increase $b$'s without increasing the $a$'s.

In all cases, $a^{p+1}b^pc^p=uvxyz$ can be pumped into a word not in $L$. So $L$ does not behave as described by the pumping lemma, which invalidate our assumption that $L$ is context free.

$\endgroup$

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.