I had to come up with a CFG for language $L_1=$$(a+b)$*$-L$
where $L =$ {$a^nb^n: n∈N$} .
So my CFG has these $S\to a\mid b\mid bS\mid Sa\mid aSb\mid bSb\mid aSa$ .
And I am pretty sure that it generates the whole $L_1$ but I don't know how to prove it.
Thank you!
Best Answer
Suppose there was a string $s \in (a | b)^*$ such that $s \notin L_1$ and $s \neq a^nb^n$ for any natural $n,$ where $s$ is of the smallest size such that there is a string which meets these conditions. ($s$ is minimal)
Clearly $|s|$ must be $1, 2,$ or greater than or equal to $2.$ The case where $|s| = 1$ is covered trivially: $a$ and $b$ are in $L_1.$
For $|s| = 2, L_1$ generates $aa$ via $S \to Sa \to aa, ba$ via $S \to bS \to ba,$ and $bb$ via $S \to bS \to bb.$ The only remaining $s$ such that $|s| = 2$ is $ab,$ but this would clearly contradict the definition of $s$ since $ab = a^1b^1.$ So, we must have $|s| > 2.$
Consider the decomposition $s = c_1wc_2,$ for $c_1, c_2 \in \{a,b\}, w \in (a|b)^*.$ Because our grammar has the rules $S \to \{aSa, aSb, bSa, bSb\},$ if $w$ is generated by our grammar then $s$ must be as well. So, because $s$ is not generated by our grammar, we must have that $w$ is not generated by our grammar, and because $s$ is minimal, we must have that $w$ is of the form $a^n b^n,$ otherwise we would have a smaller counterexample. This gives us three forms to consider for $s:$ $s = a(a^nb^n)a, s = b(a^nb^n)a,$ or $s = b(a^nb^n)b,$ noting that the form $a(a^nb^n)b = a^{n+1}b^{n+1}$ contradicts our definition of $s.$
Now, consider a string $x \in (a|b)^*$ with an odd length. By our argumentation before, if we can generate such an $x$ with length $n,$ we can generate any $x$ with length $n+2,$ so because we can generate any such $x$ with $|x| = 1,$ by induction we can show that we can generate any such $x$ with $|x| = 2k + 1, k > 0.$
So, going through our forms for $s,$ rewrite $a(a^nb^n)a$ as $(aa^nb^n)a = xa$ with $|x| = 2n+1$ for some natural $n.$ Because of our rule $S \to Sa,$ clearly we can generate strings of this form. Similarly, we can generate strings of the forms $b(a^nb^n)a = (ba^nb^n)a = xa$ and $b(a^nb^n)b = b(a^nb^nb) = bx.$ We have now covered every possible form for $s,$ showing each one either can be generated or is of the form $a^nb^n,$ so we have our contradiction and there can be no such minimal counterexample $s.$
Hope this helps!