patternMinor
A context free grammar proof
Viewed 0 times
contextgrammarprooffree
Problem
There is a problem which I cannot solve. If you give a tip I will be very glad.
Prove that following language is not context free:
$L= \{ a^nb^m | \gcd(n,m) = 1 \}$.
It can be proven using the pumping lemma, but how?
If I start with some prime numbers $m$ and $n$ where $m>n>2$ and pump it up from $uVxYz$, there are three possible outcomes: $a^{n + k} b^m$, $a^{n +k}b^{m +k}$, $a^n b^{m +k}$. Since I do not know whether $k$ is even or odd I cannot say something. It is certain that $a^n$ and $b^m$ will be odd. However after adding $k$ to some of them, how can I say something about whether their gcd is 1 or not?
Prove that following language is not context free:
$L= \{ a^nb^m | \gcd(n,m) = 1 \}$.
It can be proven using the pumping lemma, but how?
If I start with some prime numbers $m$ and $n$ where $m>n>2$ and pump it up from $uVxYz$, there are three possible outcomes: $a^{n + k} b^m$, $a^{n +k}b^{m +k}$, $a^n b^{m +k}$. Since I do not know whether $k$ is even or odd I cannot say something. It is certain that $a^n$ and $b^m$ will be odd. However after adding $k$ to some of them, how can I say something about whether their gcd is 1 or not?
Solution
Hint...
There may be a direct application of the pumping lemma, but I suggest you take a look at closure properties. Consider the non-CFL in the first answer to the reference post, $P=\{a^p:p \text{ prime}\}$, which is clearly a cousin of $L$. Can you find a (fairly simple) operation on $L$ that preserves CFLs and more or less yields $P$? If so, you are done, except perhaps to tidy up with some other operations to deal with special cases for $P$.
In general, when languages are relatively "dense", that is, have a high proportion of members to non-members for all given lengths, it's harder to apply pumping arguments, because it's more work to pump to get outside the "dense" set; in fact, sometimes it's impossible. $P$ is a nice "sparse" set, so pumping works well, as shown in the reference post. $L$ is quite a bit "denser", so transforming it to a "sparser" form is a good tactic to try.
The classical example of this principle (for non-regular languages) is the very dense set $\{a^ib^j:i \neq j\}$ and the corresponding sparse set is $\{a^ib^i\}$. The operation in this case is complement, again with a "cleanup" operation needed as well. As part of the above hint, the operation there is not complement, which doesn't work for CFLs anyway.
There may be a direct application of the pumping lemma, but I suggest you take a look at closure properties. Consider the non-CFL in the first answer to the reference post, $P=\{a^p:p \text{ prime}\}$, which is clearly a cousin of $L$. Can you find a (fairly simple) operation on $L$ that preserves CFLs and more or less yields $P$? If so, you are done, except perhaps to tidy up with some other operations to deal with special cases for $P$.
In general, when languages are relatively "dense", that is, have a high proportion of members to non-members for all given lengths, it's harder to apply pumping arguments, because it's more work to pump to get outside the "dense" set; in fact, sometimes it's impossible. $P$ is a nice "sparse" set, so pumping works well, as shown in the reference post. $L$ is quite a bit "denser", so transforming it to a "sparser" form is a good tactic to try.
The classical example of this principle (for non-regular languages) is the very dense set $\{a^ib^j:i \neq j\}$ and the corresponding sparse set is $\{a^ib^i\}$. The operation in this case is complement, again with a "cleanup" operation needed as well. As part of the above hint, the operation there is not complement, which doesn't work for CFLs anyway.
Context
StackExchange Computer Science Q#1842, answer score: 2
Revisions (0)
No revisions yet.