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

Question

●文法G=(VT，VN，P，S)的类型由G中的 (32) 决定。若G0=({a,b}，{S，X，Y}，P，S)，P中的产生式及其序号如下：

1：S→XaaY

2：X→YYlb

3：Y→XbXla

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

(32) A．VT

B．VN

C．P

D．S

(33) A．0

B．1

C．2

D．3

(34) A．图灵机

B．下推自动机

C．有限状态自动机

D．其他自动机

(35),(36) A．13133

B．12312

C．12322

D．12333

Answer 1

正确答案：C,C,B,D,C

 【解析】形式语言的文法是一个4元组G=(V_T，V_N，P，S），其中V_T是非空有限集，称为终端符集，V_N也是非空有限集，称为变量集；P为产生式集；S为起始符，S∈V_N。形式语言的文法按P的特性可分成正则文法、上下文无关文法、上下文有关文法和图灵文法4种类型，又分别称为3型、2型、1型和0型文法。所对应的可实现的自动机分别为有限状态自动机、下推自动机、线性有界自动机和图灵机。本题中给出的文法、生产式左部均是单个变量，因此是上下文无文法。由此文法导出句子aaaaa的产生式号的序列及推导过程如下：
S→XaaY1→YYaaY2→aYaaY3→aaaaY3→aaaaa 3句子baabbb的推导过程为：
S→XaaY1→baaY2→baaXbx3→baabbx 2→baabbb2因而产生式号的序列是12333和12322