一个上下文无关文法G包括哪四个组成部分?

题目

一个上下文无关文法G包括哪四个组成部分?

如果没有搜索结果或未解决您的问题,请直接 联系老师 获取答案。
相似问题和答案

第1题:

Chomsky 定义的四种形式语言文法中,1 型文法又称为( )文法。

A. 短语文法

B. 上下文无关文法

C. 上下文有关文法

D. 正规文法


参考答案:C

第2题:

上下文无关文法比正规文法有更差的描述能力。()


参考答案:错误

第3题:

●为下列文法选择最准确的答案:

文法G[S]属于 (52) :

S→CD Ab→bA

C→aCABa→aB

C→bCBBb→bB

AD→aDC→ε

BD→bDD→ε

Aa→bD

L(G)={ww|w∈{a,b}*}

文法G[P]属于 (53) :

P→0A|1B|0

A→0A|1B|0P

B→1B|1|0

文法G[I]属于 (54) :

I → lT

I → l

T → lT

T → dT

T → l

T → d

其中,l表示a~z中的任意一个英文字母,d表示0~9中的任意一个数字。

(52) ~(54) A.1型(上下文有关)文法

B.2型(上下文无关)文法

C.定义标识符的3型(正规)文法

D.0型文法


正确答案:A,B,C
【解析】本题考查4种文法的定义。需要注意的是,4个文法类的定义是逐渐增加限制的,因此每一种正规文法都是上下文无关的,每一种上下文无关文法都是上下文有关的,而每一种上下文有关文法都是0型文法。称0型文法产生的语言为0型语言。上下文有关文法、上下文无关文法和正规文法产生的语言分别称为上下文有关语言、上下文无关语言和正规语言。

第4题:

形式语言中,不包含()。

A.上下文有关文法

B.上下文无关文法

C.短语文法

D.句子文法


正确答案:D

第5题:

文法分为四种类型,即0型、1型、2型、3型。其中2型文法是()。

A.短语文法

B.正则文法

C.上下文有关文法

D.上下文无关文法


正确答案:D

第6题:

● 程序语言的大多数语法现象可用上下文无关文法描述。对于一个上下文无关文法G=(N,T,P,S),其中 N

● 程序语言的大多数语法现象可用上下文无关文法描述。对于一个上下文无关文法G=(N,T,P,S),其中 N是非终结符号的集合,T 是终结符号的集合,P是产生式集合,S 是开始符号。令集合 V= N∪T,那么 G 所描述的语言是 (50) 的集合。

(50)

A. 从 S出发推导出的包含 V中所有符号的串

B. 从 S出发推导出的仅包含 T 中符号的串

C. N中所有符号组成的串

D. T 中所有符号组成的串


正确答案:B

第7题:

一个属性文法包含一个上下文无关文法和一系列语法规则。()


参考答案:错误

第8题:

二义文法是上下文无关文法。()

此题为判断题(对,错)。


参考答案:正确

第9题:

一个上下文无关文法G包括四个组成部分,它们是:一组非终结符号,一组终结符号,一个开始符号,以及一组_____。

A.句子

B.句型

C.单词

D.产生式


正确答案:D

第10题:

已知文法G1=(VT={a,b,d},VN={S,A,B},S,P),其中P为: S→dAB A→aA|a B→bB|ε 该文法属于(28)文法。

A.0型

B.上下文有关

C.上下文无关

D.正规


正确答案:C
解析:乔姆斯基(Chomsky)把文法分成4种类型,即0型、1型、2型和3型,由此产生的语言分别称为0型、1型、2型和3型语言。这几类文法的差别在于对产生式的形式施加不同的限制,如下表所示。0型文法也称短语文法,1型文法也称上下文有关文法,2型文法也称上下文无关文法,2型文法的识别器模型是下推自动机。3型文法也称线性文法(或称正规文法),其识别器模型是有限状态自动机。文法G1的所有产生式形式都是A→β,其中A∈VN,β∈V*,且第1条规则S→dAB是非线性的,因此文法G1属于2型文法,又称上下文无关文法。