1
$\begingroup$

I am supposed to write a Context free grammar that generates the language:

$\qquad L(G) = \{0^{3n}1^{2n}0^{m}1^{m} : n \ge 1, m \ge 1\}$

I have the rules:

$$S \rightarrow 000S$$ $$S \rightarrow S11T$$ $$T \rightarrow 0T$$ $$T \rightarrow T1$$

This looks correct in terms of the structure of the grammar but I am not sure how to denote how to tell the grammar to terminate at the correct time given the conditions $n \geq 1$ and $m \geq 1$.

$\endgroup$
3
$\begingroup$

First off, your grammar isn't quite right, since there's no way to eliminate $S$; every production with $S$ on the LHS produces a string including $S$, so your grammar generates no (finite) strings at all.

To capture the "greater than or equal to 1" requirement, you should have a rule that produces the smallest permissible string; to handle the $m$ case, this would mean you need a production yielding $00011$. To handle the $n$ case, on the other hand, you'd need a production yielding $01$. Together, this implies that $0001101$ is the smallest string in your language. With the base cases out of the way, you can add other productions to build on this base case.

For your case, you have have a context-free language which is the concatenation of two other context-free languages. If you can make a grammar for the two constituent languages, it's easy to make a grammar for your language:

$$S \rightarrow S_1S_2$$

Grammars for the other are easy, too, and you had the right idea:

$$S_1 \rightarrow 00011 \mid 000S_111$$

and

$$S_2 \rightarrow 01 \mid 0S_21$$

$\endgroup$
  • $\begingroup$ Oh, so you must break up each grammar individually before-hand. and the part $S_1$ -> 00011 is the base case then? $\endgroup$ – Matt Hintzke Mar 27 '13 at 19:22
  • $\begingroup$ @MattHintzke You don't have to, of course; it just makes it easier. It's possible that there are other ways to come up with a grammar for this language that don't break it up and which yield the same (or another correct) grammar. Breaking it up is just a way to do it more easily. Note that I take a fundamentally different approach from yours, rather than pointing out how to amend your approach, since your approach didn't lead to a correct answer. If it had, showing you a different way of doing things would probably not have constituted a relevant answer. $\endgroup$ – Patrick87 Mar 27 '13 at 19:26
1
$\begingroup$

Notice that $L(G)=\{(000)^n(11)^n0^m1^m\}$.

Hint: find a grammar for $\{0^n1^n\}$

$\endgroup$
  • $\begingroup$ oh now i see what you mean. but what i don't get is how to tell the grammar that for every (000) triple in the string, there must be the same number of (11) following it $\endgroup$ – Matt Hintzke Mar 27 '13 at 19:18
  • $\begingroup$ I'll help you with that, here is a grammar for generating the language $\{a^nb^n:n\ge 1\}$: $$S\to aSb\mid ab$$. $\endgroup$ – saadtaame Mar 27 '13 at 19:20

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.