2
$\begingroup$

I want to prove that $L = \{a, b\}^* - \{(a^n b^n)^m \mid n, m \ge 1\}$ is a Context Free Language.

so far, I tried to find a Context Free Grammar for $L$ or to use properties of Context Free Languages but have not been successful yet.

Any guidance and explanation would be greatly appreciated.

$\endgroup$
3
$\begingroup$

Suppose that $w$ is in the language. We can write $w$ as a concatenation of runs: $$ w = a^{i_1} b^{j_1} a^{i_2} b^{j_2} \dots a^{i_m} b^{j_m}, $$ where all indices other than possibly $i_1,j_m$ are strictly positive.

A word of this form belongs to $(a^nb^n)^m$ if all indices are equal. Since $w$ is in the language, there must exist two indices which are different. There are several cases to consider:

  1. $w = \epsilon$.
  2. $i_1 = 0$ and $w \neq \epsilon$. In other words, $w$ starts with $b$.
  3. $j_m = 0$ and $w \neq \epsilon$. In other words, $w$ ends with $a$.
  4. $i_s \neq i_t$ for some $s < t$. The word is thus of the general form $$ (a+b)^*ba^xb^+(a^+b^+)^*a^yb(a+b)^*, $$ where $x \neq y$.
  5. $j_s \neq j_t$ for some $s < t$. This is similar to the preceding case.
  6. $i_s \neq j_t$ for some $s \leq t$. The word is thus of the general form $$ (a+b)^*ba^x(b^+a^+)^*b^ya(a+b)^*, $$ where $x \neq y$.
  7. $j_s \neq i_t$ for some $s < t$. This is similar to the preceding case.

Starting with a context-free grammar for $\{a^xb^y : x \neq y \}$ (a standard exercise – separate into cases $x<y$ and $x>y$), you can create a grammar covering all the cases above.

$\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.