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

Improve this question
$\endgroup$
0

2 Answers 2

Reset to default
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$$

Improve this answer
$\endgroup$
2
  • $\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
    Commented Mar 27, 2013 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
    Commented Mar 27, 2013 at 19:26
1
$\begingroup$

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

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

Improve this answer
$\endgroup$
2
  • $\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
    Commented Mar 27, 2013 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$
    – mrk
    Commented Mar 27, 2013 at 19:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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