问题 单项选择题

文法G=(VT,VN,P,S)的类型由C中的 (32) 决定。若GO=(a,b,S,X,Y,P,S),P中的产生式及其序号如下:

1:S→XaaY

2:X→Dqb

3:Y→XbXla

则GO为 (33) 型文法,对应于 (34) ,由GO推导出句子aaaaa和baabbb时,所用产生式序号组成的序列分别为 (35) (36)

(36)处填()。

A.13133

B.12312

C.12322

D.12333

答案

参考答案:C

解析:

形式语言的文法是一个4元组C=(VT,VN,P,S),其中VT是非空有限集,称为终端符集;VN也是非空有限集,称为变量集;P为产生式集;3为起始符,S∈VN。形式语言的文法按户的特性可分成正则文法、上下文无关文法、上下文有关文法和图灵文法4种类型,又分别称为3型、2型、1型和0型文法。所对应的可实现的自动机分别为有限状态自动机、下推自动机、线性有界自动机和图灵机。本题中给出的文法、生产式左部均是单个变量,因此是上下文无关文法。由此文法导出句子aaaaa的产生式号的序列及推导过程如下:

S→XaaY1→YYaaY2→aYaaY3→aaaaa 3

句子baabbb的推导过程为:

S→XaaY1→baaY2→baaXbx3→baabbx 2→baabbb2因而产生式序号的序列是12333和12322。

单项选择题
填空题 案例分析题