正确的线性上下文无关语法

Question

我有问题。我必须使用 alphapet={0,1} 编写正确的线性上下文自由语法，其中 0 的数字将是偶数，而数字 od 1 将是奇数。我试着写了。但它不起作用。

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.

语法应该接受偶数的 0 和奇数的 1。 当 A->wB 或 A->w 时，语法上下文自由是右线性的，其中 w 是我们字母表下的任何单词，而 A，B 不是终端

Answer 1

怎么样

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.

语法是有规律的，因为你不必记住你已经通过的部分，你只能记住每个部分的当前状态，即四种不同的状态，其中一个（奇数，偶数零）正在接受。作为常规语法，它也是右线性CFG。

Answer 2

也许是这样的？

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.

我将这个问题解释为要求 0 s 和 1 s 序列的语法，其中连续 0 s 的数量总是偶数，连续 1 s 的数量总是奇数。