문제

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