2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Luke Mathieson Oct 10 '13 at 0:35
  • $\begingroup$ Would it be $ S -> 01 | 0S1 | \epsilon$ $\endgroup$ – No Name Oct 10 '13 at 0:39
  • $\begingroup$ 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). $\endgroup$ – Luke Mathieson Oct 10 '13 at 0:44
  • 1
    $\begingroup$ 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$. $\endgroup$ – Yuval Filmus Oct 10 '13 at 1:16
  • 1
    $\begingroup$ 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. $\endgroup$ – reinierpost Oct 10 '13 at 7:36
5
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Just a query - The language generated will be Deterministic context free , right ? $\endgroup$ – Garrick Oct 22 '16 at 9:48
  • 1
    $\begingroup$ I don't know, you tell me. $\endgroup$ – Yuval Filmus Oct 22 '16 at 9:51
  • $\begingroup$ 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 ? $\endgroup$ – Garrick Oct 22 '16 at 11:00
  • $\begingroup$ You cannot; comments are not for discussion. Instead, ask your question as what it is – a question. $\endgroup$ – Yuval Filmus Oct 22 '16 at 11:01
  • 1
    $\begingroup$ Well, tough luck. Ask a local TA or a fellow student. $\endgroup$ – Yuval Filmus Oct 22 '16 at 11:06
2
$\begingroup$

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$.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.