Context Free Grammar for $\{0^n1^n \mid n \geq 0\}^*$

Give a context free grammar for the following language over $\Sigma = \{0,1\}$:
$L = L_1^*$ where $L_1 = \{0^n1^n : n \geq 0\}$.

Not really sure where to start with this one. Any help is appreciated

• One first step is to build a grammar that just does the $L_{1}$ part. If you're being asked this question, you most likely have seen a such a grammar before. – Luke Mathieson Oct 10 '13 at 0:35
• Would it be $S -> 01 | 0S1 | \epsilon$ – No Name Oct 10 '13 at 0:39
• That would work, now you can use that as a building block, and repeat it as many times as you want (including possibly zero times). – Luke Mathieson Oct 10 '13 at 0:44
• Hint: For each context-free language $L_1$, the language $L = L_1^*$ is context-free. In fact, given a grammar for $L_1$, you only need to add two rules in order to get $L$. – Yuval Filmus Oct 10 '13 at 1:16
• Please, state your question in the title! If you can't, that's a strong indication that what you're dumping here is not actually a question of your own, but a question someone else posed to you that you want someone else to answer for you. Don't do that. – reinierpost Oct 10 '13 at 7:36

Hints:

1. Start with a context-free grammar for $L_1$.

2. Modify it to a context-free grammar for $L = L_1^*$. There is a simple transformation which works for any context-free language $L_1$ and any context-free grammar generating it.

• Just a query - The language generated will be Deterministic context free , right ? – Garrick Oct 22 '16 at 9:48
• I don't know, you tell me. – Yuval Filmus Oct 22 '16 at 9:51
• Sir, yes i tried to make a DPDA for it and it contains 3 states, so i think it is DCFL. Can you please tell me how to add photos here in the comments so that i can show you ? – Garrick Oct 22 '16 at 11:00
• You cannot; comments are not for discussion. Instead, ask your question as what it is – a question. – Yuval Filmus Oct 22 '16 at 11:01
• Well, tough luck. Ask a local TA or a fellow student. – Yuval Filmus Oct 22 '16 at 11:06

As others have pointed out, the first step is to get $L_1$. After that, constructing $L$ is straightforward. You've already given a correct grammar for $L_1$: $S \rightarrow 01 \mid 0S1 \mid \epsilon$. Of course, you could simplify this grammar a bit: $S \rightarrow \epsilon \mid 0S1$. However, the grammar you give is perfectly fine.

Now, $L_1^*$ means any number of strings from $L_1$ concatenated together. From the grammar we already have, the nonterminal symbol $S$ can derive all strings in $L_1$. So, we need a grammar capable of generating $S^* = \epsilon$, $S$, $SS$, ..., $S^n$, ... Try to show that the grammar $S' \rightarrow \epsilon \mid SS'$ works.

Once you show (a) that your grammar works, and (b) the grammar in the second paragraph generates $S^*$, you should be able to put these grammars together to form a single grammar with two nonterminal symbols ($S$ and $S'$) which generates $L$.

• Very nice explaination. Just a query - The language generated will be Deterministic context free , right ? – Garrick Oct 21 '16 at 17:58