1
$\begingroup$

Consider the language $L \subseteq \{a,b,c\}^*$, where $w \in L$ if and only if the ratio of the number of $a$'s in $w$ to the number of $b$'s in $w$ is an integer. I've been unable to find a counterexample string in $L$ which I can use to disprove (via a contradiction proof using the pumping lemma for CFLs) that $L$ is a CFL. This suggests that $L$ may be recognized by a nondeterministic PDA.

Now, if $\#_a(w) = i\cdot \#_b(w)$ for some $i \geq 0$, then I can perfectly match every single $b$ with $i$ $a's$. The problem is that since $i$ can be any nonnegative integer, there are strings in $L$ for which I'd need to match every one $b$ with one $a$, strings for which I'd need to match every two $a$'s with one $b$, and so on. I don't see how a nondeterministic PDA has the capacity to cover all such (i.e., infinitely many) matchings.

$\endgroup$
0

2 Answers 2

2
$\begingroup$

The language is not a CFL. The string $w$ that is the counter example to the pumping lemma is $a^{(N+1)^2}b^{(N+1)}$ where $N\geq 1$ is the pumping length. The idea is to take the number of $a$'s comparably larger by an order of $N$ to the number of $b$'s. Then if you pump you get strings with $\#_a={(N+1)^2+ik_1}$ and $\#_b ={N+1+ik_2}$ for $i\geq -1$. You would be able to prove that his string does not belong to $L$ for some $i$ and for any $k_1+k_2\leq N$.

Or if we take some crazy long string like $w = a^{(2N)!}b^{N+1}$, noting that the pumped string will have $\#_a={(2N)!+ik_1}$ and $\#_b={N+1+ik_2}$ for $i\geq -1$. If $k_1 = 0$ then we can take $i > \frac{(2N)! - N -1}{k_2}$. If $k_1 > 0$ then for $i=1$, $\frac{(2N)!+k_1}{N+1+k_2}$ is a proper fraction, since $0\leq k_2 \leq N-1$, $1 \leq k_1 \leq N$ and therefore $N+1 \leq N+1+k_2 \leq 2N$ which implies $0<\frac{k_1}{N+1+k_2}<1$ is a fraction.

$\endgroup$
5
  • $\begingroup$ How do we know that $\frac{(N+1)^2 + k_1}{N+1 + k_2}$ is not an integer? $\endgroup$ Mar 23, 2016 at 2:02
  • $\begingroup$ Sorry for $i=1$ the fraction is not always an integer. You will need to take a large value of $i$. $\endgroup$ Mar 23, 2016 at 2:30
  • $\begingroup$ Just a nit to pick: when pumping, the number of $a$ and $b$ are as you state, but you can end up with a mixture of $a$ and $b$, not clean $a$s then $b$s. $\endgroup$
    – vonbrand
    Mar 23, 2016 at 16:11
  • $\begingroup$ @DavidSmith, that is precisely the point. That fraction can't be an integer for all $i$. $\endgroup$
    – vonbrand
    Mar 23, 2016 at 16:13
  • 1
    $\begingroup$ @vonbrand, I will modify the answer to reflect mixed strings. $\endgroup$ Mar 23, 2016 at 17:21
1
$\begingroup$

You could use Parikh's theorem. Suppose that your language is context-free. Then its commutative image $$ c(L) = \{(|u|_a, |u|_b, |u|_c) \mid u \in L \} = \{ (rn, n, m) \mid r >0, n \geqslant 0, m \geqslant 0\} $$ would be a semilinear set of $\mathbb{N}^3$. By projection, the set $R = \{ (rn, n) \mid r >0, n \geqslant 0\}$ would be a semilinear set of $\mathbb{N}^2$. Observe that $$ \{ (rn, n) \mid r >1, n > 1\} = R \setminus ( S \cup T) $$ with $S = \{ (n, n) \mid n \geqslant 0\}$ and $T = \{ (r, 1) \mid r >0\})$. Since $S$ and $T$ are semilinear and since semilinear sets are closed under Boolean operations, the set $\{ (rn, n) \mid r >1, n > 1\}$ would be semilinear. Thus its projection $\{ rn \mid r >1, n > 1\}$ would be a semilinear set of $\mathbb{N}$, and so would be its complement $\{0,1\} \cup \{ p \mid p \text{ is prime }\}$, which is certainly not the case. Thus $L$ is not context-free.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.