3
$\begingroup$

Hey so I am currently stuck on a question regarding context free grammars. Here is the question:

Construct a context-free grammar for the language L1 = {w1#w2 | w1 and w2 contain the same number of ones} and provide a derivation for the string w = 1001010#111.

I know the grammar should start out like:

S -> S1 # S1

S1 -> ?

I'm not sure how to make each word have the same number of ones. Any suggestions?

$\endgroup$
1
  • 4
    $\begingroup$ Why was this migrated to mathematica.SE? I don't see any relation to Mathematica at all. $\endgroup$ – celtschk May 2 '12 at 12:56
1
$\begingroup$

As a hint, your first step is incorrect. Once you've tried building each side independently, you will not have a way to ensure that they have the same number of 1s.

Instead, try building the string from the outside inward. If you were going to put 0s and 1s into each half of the string, how would you ensure that you did so in a way that always ensured that the number of 0s and 1s was the same?

Hope this helps!

$\endgroup$
5
  • $\begingroup$ Thank you for the insight, that does make the problem much different. To create a CTG with the same number of 0s and 1s would be S-> 0S1 | 1S0 | SS, correct? This is a little different from my problem though. $\endgroup$ – Josh May 2 '12 at 0:07
  • $\begingroup$ @JoshNeal- The hint I gave directly applies to the problem you're trying to solve. Don't think of the problem as building up two separate strings in parallel. Instead, think about trying to construct both strings simultaneously, building the left side of the first string at the same time that you build the right side of the second string. Does that help? $\endgroup$ – templatetypedef May 2 '12 at 0:15
  • $\begingroup$ It does thank you. I have gotten to the solution of S-> 1S1 | SS | 0 | #. Does this look correct to you? Thank you for the help! $\endgroup$ – Josh May 2 '12 at 0:25
  • $\begingroup$ @JoshNeal- That doesn't quite work; I can generate the string ######, for example. You're on the right track, though. Is there any reason you're attached to the S -> SS production? $\endgroup$ – templatetypedef May 2 '12 at 0:48
  • $\begingroup$ I had just been using S-> SS so that I could create strings of whatever length necessary. Without it I wouldn't be able to create strings like 1001010#111, where the 1's and 0's are mixed. I could be wrong but removing that production would only allow for strings of the pattern 1100011. To get rid of the #### do I need to create a substring? I'm not exactly sure how to fix this problem. $\endgroup$ – Josh May 2 '12 at 1:02
0
$\begingroup$

L1 = {w1#w2 | w1 and w2 contain the same number of ones} and provide a derivation for the string w = 1001010#111.

S -> 0S (rule 1) S -> S0 (rule 2) S -> 1S1 (rule 3) S -> # (rule 4)

S -(r3)-> 1S1 -(r1)-> 10S1 -(r1)-> 100S1 -(r3)-> 1001S11 -(r1)-> 10010S11 -(r3)-> 100101S111 -(r1)-> 1001010S111 -(r4)-> 1001010#111

$\endgroup$

Your Answer

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