博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
0型文法、1型文法、2型文法、3型文法 的判定
阅读量:4647 次
发布时间:2019-06-09

本文共 1029 字,大约阅读时间需要 3 分钟。

引用: 

==================== 
S-> aaS|a是什么型的,为什么 
S-> aSb|ab是什么型的,为什么 
S-> SaS|b是什么型的,为什么 
===================== 
答:三种文法都属于上下文无关文法。 
四种文法的判断非常简单,说到到,四种文法就是规定产生式的左和右边的字符的组成规则不同而已,其它的不能理解就不要去想了,你只要知道判断的时候就是以产生式的左边和右边符合的规则进行判断。下面解释一下如何根据产生式左边和右边的特征来进行判断。 
首先,应该明确,四种文法,从0型到3型,其规则和约定越来越多,限制条件也越来越多,所以,我们判断时可以从最复杂的3型进行判断,依次向下判断,如果不符合3型的,那再看是不是2型的,不是2型的,再看是不是1型的,当然,对于作题作的熟的朋友,不用这么复杂,可以一眼直接看出来。 
3型文法遵循什么规范呢? 
第一点:左边必须只有一个字符,且必须是非终结符; 
第二点:其右边最多只能有两个字符,且当有两个字符时必须有一个为终结符而另一个为非终结符。当右边只有一个字符时,此字符必须为终结符。 
第三点:对于3型文法中的所有产生式,其右边有两个字符的产生式,这些产生式右边两个字符中终结符和非终结符的相对位置一定要固定,也就是说如果一个产生式右边的两个字符的排列是:终结符+非终结符,那么所有产生式右边只要有两个字符的,都必须前面是终结符而后面是非终结符。反之亦然,要么,就全是:非终结符+终结符。 
依以上规则判断,你所给的三个文法显然都不属于3型文法。 
再看2型文法如何判断: 
第一点:与3型文法的第一点相同,即:左边必须有且仅有一个非终结符。 
第二点:2型文法所有产生式的右边可以含有若干个终结符和非终结符(只要是有限的就行,没有个数限制)。 
依2型文法的判断规则,你的三个文法都属于2型文法,即:上下文无关文法。 
再看1型文法如何判断: 
第一点:1型文法所有产生式左边可以含有一个、两个或两个以上的字符,但其中必须至少有一个非终结符。 
第二点:与2型文法第二点相同。 
依1型文法判断规则,显然,你的文法也是属于1型的。 
最后是0型文法,这个就不用看了,只要你能描述出来,都属于这个类型,即0型。 
所以,取其最高的符合规则,最后的答案是其符合:上下文无关文法规则,即2型。

转载于:https://www.cnblogs.com/yfz1552800131/p/8615385.html

你可能感兴趣的文章
WPF图标拾取器
查看>>
通过取父级for循环的i来理解闭包,iife,匿名函数
查看>>
HDU 3374 String Problem
查看>>
数据集
查看>>
[Leetcode] unique paths ii 独特路径
查看>>
HDU 1217 Arbitrage (Floyd + SPFA判环)
查看>>
IntelliJ idea学习资源
查看>>
Django Rest Framework -解析器
查看>>
ExtJs 分组表格控件----监听
查看>>
Hibernate二级缓存配置
查看>>
LoadRunner常用术语
查看>>
关于jedis2.4以上版本的连接池配置,及工具类
查看>>
记忆讲师石伟华微信公众号2017所有文章汇总(待更新)
查看>>
mechanize (1)
查看>>
FactoryBean
查看>>
Coolite动态加载CheckboxGroup,无法在后台中获取
查看>>
如何在我们项目中利用开源的图表(js chart)
查看>>
nfs服务器工作原理
查看>>
C3P0连接池工具类使用
查看>>
SVN常用命令备注
查看>>