在形式语言中,文法G是一个四元组G=(VN,Vr,P,Z),其中VN为(6)。若文法C的产生式集P为: (1)Z→Bc (2)Z→Zc (3)B→Ab (4)B→Bb (5)A→Aa (6)A→a 则文法G是(7)文法,识别G

admin2009-02-15  34

问题 在形式语言中,文法G是一个四元组G=(VN,Vr,P,Z),其中VN为(6)。若文法C的产生式集P为:
(1)Z→Bc    (2)Z→Zc    (3)B→Ab    (4)B→Bb    (5)A→Aa    (6)A→a
则文法G是(7)文法,识别G的自动机为(8)。对于G来说,(9)为文法G可接受的字符串,(10)为文法G不可接受的字符串。
供选择的答案:

选项 A、状态标志符
B、开始符
C、语句集
D、非终结符集合

答案D

解析 形式语言首先于 1956年由Chomsky进行描述。该理论讨论了语言与文法的数学理论,按照对文法规则的不同定义形式,对语言和文法进行了分类。一般来说,Chomsky文法是一个四元组G=(VN,Vr,P,Z),其中VN为非终结符集合,Vr为由终结符组成的字母表集合,P是有穷非空的重写规则集合,Z是识别符号。文法 G对应的语言是能从该文法的识别符号产生的那些终结符号串(句子)组成的集合。
简单来说,对于文法的分类分为4类:
0型文法也称短语结构文法可以由图灵机识别。
1型文法也称上下文有关文法,可以由线性界限自动机识别。
2型文法也称上下文无关文法,可以由下谁自动机识别。
3型文法也称正则文法可以由有穷状态自动机识别。
具体的文法定义可以参照编译原理中的相关概念。
某种文法可以接受的句子经过简单推理即可。
转载请注明原文地址:https://jikaoti.com/ti/kbJ7FFFM
0

相关试题推荐
最新回复(0)