Right linear context free grammar with even difference of 0's and 1's

Question

I'm trying to write a right linear context free grammar, in which the difference between numbers of 0's and 1's should be even. For example:

010001 = 4 - 2 = 2 (even)

I had a similar problem. Maybe it will help! I'm trying to write it on prolog. I did other 10 exercises but this is too difficult for me. Any ideas on how to do it?

my code

s --> [].
s --> [1],a.
s --> [0],b.

a --> [1],s.
a --> [0],c.

b --> [1],c.
b --> [0],s.

c --> [].
c --> [1],b.
c --> [0],a.

It's work for many cases but I'm not sure if it is well.

People at stackoverflow don't do homeworks. If you have a question concerning your exercise, you should show us what you've tried so far, and what isn't going as expected. — Rubens

Sergii Dymchenko Sergii Dymchenko · Accepted Answer · 2014-04-07T06:41:47

The problem can be greatly simplified with a little math.

Let a be number of 0, b - number of 1, n - length of a word. We want abs(a - b) to be even.

Do the math:

a + b = n
b = n - a
a - b = a - n + a = 2*a - n

2*a is always even, so abs(a - b) is even iff n is even.

So the task is really just to check if the length of the word is even.

Solution:

s --> [].
s --> digit, digit, s.
digit --> [0].
digit --> [1].

Right linear context free grammar with even difference of 0's and 1's

1 Answers