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

有帮助吗?

解决方案

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.

其他提示

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.

许可以下: CC-BY-SA归因
不隶属于 StackOverflow
scroll top