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?
Best Answer
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!