正确的线性上下文无关文法 [英] right linear context free grammar

查看:97
本文介绍了正确的线性上下文无关文法的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!

问题描述

我有问题。我必须使用alphapet = {0,1}编写正确的线性上下文无关文法,其中数字0为偶数,数字od 1为奇数。我尝试写某事。

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.

语法应接受偶数0和奇数1。当A-> wB或A-> w时,上下文无关的语法是线性的,其中w是我们字母下的任何单词,而A,B是没有终结符

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

推荐答案

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。

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.

这篇关于正确的线性上下文无关文法的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!

查看全文
登录 关闭
扫码关注1秒登录
发送“验证码”获取 | 15天全站免登陆