A grammar for the complement of language $L=\{a^{t+3}b^t:t \ge 0\}$

Question

Assume that the language $L=\{a^{t+3}b^t:t \ge 0\}$ is given.
Q1 : How can we write a grammar for the complement of this language?
Q2 : Assume that $L'=\{a^nb^m:n\ge0,m\gt n\}$ is given. Can you write a grammar for $L'\cap L$?

Note: I can easily write a grammar like this for the language $L$ itself.

S->aaaP
P->aPb
P->E

Also, I can easily write the grammar for $L'$:

S->PbX
X->bX
X->E
P->aPb
P->E

In these grammars, by E , i mean the empty string.
The first problem is the complementation and the second one is that i don't know how strings are made in the language $L' \cap L$ .

Thanks in advance.

Answer 1

Corrected HINT: Everything matching the regular expression

$$b^*+ab^*+aab^*+aaaaa^*+(a+b)^*ba(a+b)^*\tag{1}$$

is in the complement of $L$, and it’s easy to write a grammar for this part of the complement. Every string in the rest of the complement begins with $aaa$, contains at least one $b$, and does not contain the string $ba$, so it must be $a^nb^m$ for some $n\ge 3$ and $m\ge 1$. You can handle this part of the complement by breaking it into two parts:

• strings of the form $a^{n+3}b^m$ such that $1\le m<n$, those that have too few $b$s; and
• strings that begin $a^{n+3}b^m$ such that $0\le n<m$, those that have too many $b$s.

Those in the first part must begin with at least $5$ $a$s; you can get them with

$$\begin{align*} &S\to aaaaaFbX\\ &F\to aFb\mid A\\ &A\to aA\mid\epsilon\\ &X\to aY\mid a\mid\epsilon\\ &Y\to aY\mid bY\mid\epsilon \end{align*}$$

See if you can work out a grammar for the other part and combine it with a grammar for the regular expression $(1)$ to get the desired grammar for the complement of $L$.