Find the grammar and the language that is generated $L=L_1 - {L_4}^c$

41 Views Asked by At

$L_1 = \{a^nb^m: n\geq 1; m<n\}$

is generated by the following

$S_1\to A_1B_1$

$A_1\to aA_1|a$

$B_1\to aB_1b|\lambda$

and

$L_4 = \{a^nb^{n-3}: n\geq 3\}$

is generated by the following

$S_4\to a^3A_4$

$A_4\to aA_4b|\lambda$

So Given $L=L_1 - {L_2}^c$

I know $L_1 - {L_4}^c= L_1\setminus{L_4}^c= L_1 \cap {L_4}^{c^c}= L_1 \cap L_4$

Where I am not sure is about the grammar and the language it produces.

Would the grammar be something like this

$S \to S_1S_4$

$S_1\to A_1B_1$

$A_1\to aA_1|a$

$B_1\to aB_1b|\lambda$

$S_4\to a^3A_4$

$A_4\to aA_4b|\lambda$

Any help would be appreciated.

1

There are 1 best solutions below

0
On BEST ANSWER

Since $L_1 \cap L_4 = L_4$, the answer is easy.