首页 文章

正确的线性上下文自由语法

提问于
浏览 次
0

我有一个问题 . 我必须使用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是没有终端

prolog grammar context-free-grammar dcg

2 回答

  • 1

    也许是这样的？

    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 的数量始终是偶数，连续 1 的数量总是奇数 .

    回复于
  • 0

    怎么样

    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 .

    回复于

相关问题