patternMinor
Why is the following language not context-free?
Viewed 0 times
whythefreelanguagefollowingcontextnot
Problem
$L = \{a^n b^m | m \not= n^2 \}$
I guess I need to use Pumping Lemma for CFL in order to prove this. But I'm stuck.
Assuming that $ a^n b^m = uvxyz$, we know that $v$ or $y$ can not have both $a$ and $b$ symbols in them. Otherwise pumping would generate strings not of the form $a^i b^j$.
Hence both $v$ and $y$ must consist only of one kind of symbol each.
Beyond this I wonder what string in $L$ has to be chosen in order to pump and obtain something of the form $a^n b^{n^2}$.
Alternative idea : Assuming that $L$ is context-free, then I must have a PDA accepting it by final state. Can I say that this PDA can be adjusted* to accept $L'$ i.e., all $a^n b^{n^2}$ ? However I know that $L'$ is not a CFL. Hence, contradiction ?
*Adjusted = Make the non-final state on reading $a^n b^{n^2}$ as final and the rest as all non-final.
I guess I need to use Pumping Lemma for CFL in order to prove this. But I'm stuck.
Assuming that $ a^n b^m = uvxyz$, we know that $v$ or $y$ can not have both $a$ and $b$ symbols in them. Otherwise pumping would generate strings not of the form $a^i b^j$.
Hence both $v$ and $y$ must consist only of one kind of symbol each.
Beyond this I wonder what string in $L$ has to be chosen in order to pump and obtain something of the form $a^n b^{n^2}$.
Alternative idea : Assuming that $L$ is context-free, then I must have a PDA accepting it by final state. Can I say that this PDA can be adjusted* to accept $L'$ i.e., all $a^n b^{n^2}$ ? However I know that $L'$ is not a CFL. Hence, contradiction ?
*Adjusted = Make the non-final state on reading $a^n b^{n^2}$ as final and the rest as all non-final.
Solution
Your first approach is not very clear. What are $n$ and $m$? You have to fix a word in order to use the Pumping lemma; please see our reference question for how it's done.
Your second approach is fundamentally flawed as CFL is not closed against complement, i.e. your PDA construction does not work. Also, note that $L^c$ does not only contain words of the form $a^nb^{n^2}$, but also all that do not match $a^b^$.
Towards showing that $L$ is not context-free, note that $\mathrm{CFL} \cap \mathcal{L}(a^ b^)$ is closed against complement (see here). Therefore, if $L$ was context-free so would be
$\qquad L' = \{a^n b^m \mid m = n^2\}$.
It is easy to show that $L'$ is not context-free by using the Pumping lemma.
Your second approach is fundamentally flawed as CFL is not closed against complement, i.e. your PDA construction does not work. Also, note that $L^c$ does not only contain words of the form $a^nb^{n^2}$, but also all that do not match $a^b^$.
Towards showing that $L$ is not context-free, note that $\mathrm{CFL} \cap \mathcal{L}(a^ b^)$ is closed against complement (see here). Therefore, if $L$ was context-free so would be
$\qquad L' = \{a^n b^m \mid m = n^2\}$.
It is easy to show that $L'$ is not context-free by using the Pumping lemma.
Context
StackExchange Computer Science Q#11106, answer score: 2
Revisions (0)
No revisions yet.