right linear context free grammar

0
votes

I've a problem. I have to write right linear context free grammar with alphapet={0,1} where the numbers of 0 will be even and the numbers od 1 will be odd. I tried write sth. but it's doesn't work.

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

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

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

b --> [0],k.
b --> [1],d.

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

k --> [].
k --> s.

Grammar should accept even amount of 0s and odd amount of 1s. Grammar context free is right linear when A->wB or A->w where w is any word under our alphabet and A,B is no terminals

2
prologgrammarcontext-free-grammardcg
What should the grammar accept, even or odd numbers? Or even/odd amount of 1s/0s? Both actually sounds like regular grammar, not context free... – Tomas Pastircak
@TomasPastircak Could you explain why these grammars are regular? That would help a lot! – Wouter Beek

2 Answers

1
votes

How about

s --> [1],oddOnesEvenZeros.
s --> [0],oddZerosEvenOnes.

oddOnesEvenZeros--> [].
oddOnesEvenZeros--> [1],s.
oddOnesEvenZeros--> [0],oddZerosOddOnes.

oddZerosEvenOnes--> [1],oddZerosOddOnes.
oddZerosEvenOnes--> [0],s.

oddZerosOddOnes --> [1],oddZerosEvenOnes.
oddZerosOddOnes --> [0],oddOnesEvenZeros.

The grammar is regular because you don't have to remember the parts you have already passed, you can only remember current state of each, i.e. four different states, from which one (odd ones, even zeros) is accepting. As a regular grammar, it is right linear CFG as well.

0
votes

Maybe something like this?

s --> [].
s --> even_zeros, s.
s --> odd_ones, s.

even_zeros([0,0], []).
even_zeros, [X] --> [0,0,X], {X \== 0}.
even_zeros --> [0,0], even_zeros.

odd_ones([1], []).
odd_ones, [X] --> [1,X], {X \== 1}.
odd_ones --> [1,1], odd_ones.

I've interpreted the question as asking for a grammar of sequences of 0s and 1s, where the number of consecutive 0s is always even and the number of consecutive 1s is always odd.