1

Can anyone give me the thought process involved in developing a context free grammar for this? I'm given a language where there are a certain number of 0's and a certain number of 1's but the number of 0's is not equal to the number of 1's. However the 0's come first then the 1's (that should make things more straight forward). So an acceptable string would be 0000111 or 01111111

I don't want you to just give me the direct answer, or the answer at all for that matter. Just the process of figuring it out.

user2853262
  • 43
  • 1
  • 6
  • 1
    `Give me the thought process involved in developing a context free grammar`: I suggested some tricks here: [Tips for creating Context free grammar](http://stackoverflow.com/questions/15126824/tips-for-creating-context-free-grammar/15130451#15130451) – Grijesh Chauhan Oct 10 '13 at 04:32
  • 1
    then you also like read [this 'Grammar in formal languages's basics'](http://stackoverflow.com/questions/15989197/why-the-need-for-terminals-is-my-solution-sufficient-enough/15989998#15989998) – Grijesh Chauhan Oct 11 '13 at 15:16

1 Answers1

3

Well, the direct answer which you don't want is:

S - initial symbol
S -> X | Y
X -> 0X1 | X1 | 1
Y -> 0Y1 | 0Y | 0

It's the first thing that comes to mind so there isn't too much of a process. Anyway, I would say that the very first thing you must see is that there are two possibilities - either you have more ones, or zeroes and it's good two divide the problem into these two (as I divided S into X and Y).

Then you see that "context free" makes it impossible to control the number in any place other than the boundary between zeroes and ones. The you just get the idea and write down the solution.

Bartosz Marcinkowski
  • 6,651
  • 4
  • 39
  • 69