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?

  • 4
    Why was this migrated to mathematica.SE? I don't see any relation to Mathematica at all.2012-05-02

2 Answers 2

1

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!

  • 0
    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.2012-05-02
0

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