# Find the Context Free Grammar

Let $\Sigma = \{a, b\}$. For each of the following languages, find a grammar that generates it.

(a) $L_1 = \{a^n b^m : n\geq 0, m>n\}$

(b) $L_1^3$

(C) $L_1^*$

I know the grammar for the language $L_1$, that is

$S \rightarrow aSb \mid bA$
$A \rightarrow bA \mid \epsilon$

b) Introduce a new start symbol $S_1$ and a new production rule $S_1 \rightarrow SSS$
c) Introduce a new start symbol $S_2$ and a new production rule $S_2 \rightarrow S_2S \mid \epsilon$
• Can I write $L1^3$ as $L1^3$ = {$a^nb^m a^p b^q a^r b^s : n, p, r >=0, m>n, q>p, s>r$} ? how to write L1*? – Manu Thakur Aug 31 '17 at 21:29
• Just Kleene closure of $L_1$ – fade2black Sep 1 '17 at 0:28