finding grammar for languages

Question

Situation: So I have three languages.

a) $L_1 =$ { $a^{2n-1}b^{2m} | n,m \geq 1$}

b) $L_2 =$ { $a^nb^ma^nb^m | n,m \geq 1$}

c) $L_3=$ { $a^nb^ma^{n+m} | n \geq 1, m \geq 0$}

So one of this languages is regular, one is context-sensitive, one is context-free.

My work:

for a) I found a context-free grammar:

$S \rightarrow aTbb $

$ T \rightarrow aaTbb| \varepsilon | aaT | Tbb $

edit: found a regular grammar for a). So my problem is only b).

For b) I tried so many grammars, but they did not represent the language $L_2$. My assumption is that this grammar is context-sensitive.

c)

$ S \rightarrow aSa|B $

$ B \rightarrow bBa| \varepsilon $

Answer 1

Yes, the language $L_2$ in (b) is context-sensitive. That language $L_2$ is actually often used as an example of a context-sensitive language; the Wikipedia article https://en.wikipedia.org/wiki/Context-sensitive_grammar discusses that language and shows several example grammars for it.

You are told that $L_2$ is either regular, context-free, or context-sensitive. How do you prove which one it is?

1. Recall that regular languages are a special subset of context-free languages. Context-free languages are a special subset of context-sensitive languages.

2. So if you can prove that $L_2$ isn't context-free, that will also prove that isn't regular either. In this homework problem, the only other option is context-sensitive, which means you'll have proved your answer by process of elimination.

3. To prove that a language is not context-free, you can use the specialized "pumping lemma for context-free languages". This involves a proof by contradiction:

   • Suppose $L_2$ is a context-free language. Then, because of the pumping lemma, it must have a pumping length $p$.
   • Consider the string $\sigma=\mathtt{a}^p\mathtt{b}^{2p}\mathtt{a}^p\mathtt{b}^{2p}$ which is in the language and which has been defined in terms of this supposed pumping length $p$.
   • The pumping lemma says that if the language is really context free with a pumping length $p$, then any string of length $p$ or greater can be decomposed in a certain special way. We've carefully chosen a string $\sigma$ that can't be decomposed in this way. By proving that it can't be decomposed no matter how you try, we'll prove that there really is no pumping length $p$, so the language really isn't context-free.
   • So: by the pumping lemma, we should be able to decompose $\sigma$ into the special form $x\,w_1\,y\,w_2\,z$, with special conditions $|w_1w_2|>0$, $|w_1yw_2| \leq p$, such that every pumped string $x\,w_1^k \, y \, w_2^k\, z$ is still in the language.
   • You can see that, for this language $L_2$ in particular, that kind of pumping could only be possible if $w_1$ and $w_2$ are equal and made up of a single repeated letter. That way, $w_1$ can be in the left half of the string and $w_2$ can be in the right half of the string, and when you pump them, the string continues to be of the form $\mathtt{a}^m\mathtt{b}^{n}\mathtt{a}^m\mathtt{b}^{n}$.
   • Unfortunately, we picked a string $\sigma$ which is long enough to show how this process breaks down. We are required to have $|w_1yw_2|\leq p$. But this is so short, either $w_1yw_2$ occurs totally in the left half of the string, or it occurs totally in the right half of the string, or it spans the middle, in which case $w_1$ has $\mathtt{b}$ in it and $w_2$ has $\mathtt{a}$ in it. Either way,we've broken one of the requirements.
   • So it is not possible to decompose the string $\sigma$ into the special pumpable form, no matter how you do it.
   • Because we found a string that is un-pumpable, we conclude that the language is not context-free. Hence it is also not regular. In this homework problem, the only other option is that it is context-sensitive.