●文法G=(VT，VN，P，S)的类型由G中的 (32) 决定。若G0=({a,b}，{S，X，Y}，P，S)，P中的产生式及其序号如下：1：S→XaaY2：X→YYlb3：Y→XbXla则G0为 (33) 型文法，对应于 (34) ，由G0推导出句子aaaaa和baabbb时，所用产生式序号组成的序列分别为 (35) 和 (36) 。(32) A．VTB．VNC．PD．S(33) A．0B．1C．2D．3(34) A．图灵机B．下推自动机C．有限状态自动机D．其他自动机(35),(36) A．13133
题目
●文法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
相似考题
更多“●文法G=(VT,VN,P,S)的类型由G中的 (32) 决定。若G0=({a,b},{S,X,Y},P,S),P中的产生式及其序号如下 ”相关问题
-
第1题：
已知文法G2=(VT={a，'，'，(,)}，VN={S，L)，S,P)，其中P为 S→(L)|a L→-L，s|s 与G2等价的不含左递归规则的文法是(29)。
A．G21=(VT={a，'，'，(,)}，VN={S，L}，S，P)，其中P为 S→(L)|a L→S，S|S
B．G22=(VT＜a，'，'，(,)}，VN={S，L，L'}，S，P)，其中P为 S→(L)|a L→SL' L'→SL'|ε
C．G23=(VT{a，'，'，(,)}，VN={S，L，L'}，S，P)，其中P为 S→(L)|a L→SL' U→,SL'|ε
D．G24=(VT=(a，'，'，(,)}，VN=＜S，L，L'}，S，P)，其中P为 S→(L)|a L→SL' L→SL'|S
正确答案：C
解析：采用自顶向下的预测分析法首先是等价改写给定的文法，消除文法的左递归和提取产生式的公共左因子。消除直接左递归的方法如下：若A→Aα|β，其中α，β∈(VT∪VN)*，β不以A开始，则关于A的这种形式的产生式可改写成A→βA'A'→αA'|ε一般而言，假设A的产生式为A→Aα1|Aα2|…|Aαn|β1|β2|…|βm其中αI(i=1，2，…，n)不等于ε，βj(j=1，2，…，m)不以A开始，那么上述产生式可改成A→β1A'|β2A'|…|βmA'A'→α1A'|α2A'|…|αnA'|ε消除文法G2中规则的左递归后，其规则变成S→(L)|aL→SL'L'→，SL'|ε -
第2题：
设语言L={w|w∈{a,b}+且w中a和b的个数相等}，产生语言L的上下文无关文法是(28)。
A．Ga=(VT={a,b}，VN={S，A，B}，S,P)，其中P为， S→a|aA|bSS A→aB|bS B→b|bA|aBB
B．Gb=(VT={a,b}，VN={S,A,B}，S,P)，其中P为， S→b|bB|aSS B→aS|bA A→a|aB|bAA
C．Gc=(VT={a,b}，VN{S,A,B}，S,P)，其中P为， S→aB|bA A→a|aS|bAA B→b|bS|aBB
D．Gd=(VT={a,b}，VN={S，A，B}，S,P)，其中P为， S→aB|bA|s A→aS|bAA B→bS|aBB
正确答案：C
解析：字母表{a,b}上的任何非空串，从其所含a和b的个数来划分，分成下面3个集合：①a和b的个数相等：②a比b的个数多，但仅要a比b的个数多1个的那些子串；③b比a的个数多，但仅要b比a的个数多1个的那些子串。通过上面的分析，根据用文法规则产生句子的原理，设3个非终结符号，不妨称做S、A、B，它们的产生式分别完成：①用S的产生式推导出a和b的个数相等的串；②用A的产生式推导出a比b的个数多1个的串；③用B的产生式推导出b比a的个数多1个的串。根据3个非终结符号S、A、B的含义，显然，关于S的产生式应该是S→aB|bA。对于A产生的串，若第1个字符是a，则剩下的是a和b的个数相等的串：若第1个字符是b，则跟随b的是a比b的个数多2个的串，这个串是两个a比b的个数多1个的子串。根据上述分析，写出关于A的产生式A→a|aS|bAA。可以通过和A类似的分析，写出关于B的产生式B→b|bS|aBB。可以用归纳法证明上面所写的文法是正确的。现在，我们很清楚被选答案中的4个文法所描述的语言，它们分别是：L(Ga)={w|w∈{a,b}+且w中a比b的个数多一个}L(Gb)={w|w∈{a,b}+且w中b比a的个数多一个}L(Gc)={w|w∈{a,b}+且w中a和b的个数相等}L(Gd)={w|w∈{a,b}+且w中a和b的个数相等} -
第3题：
己知文法G2=(VT＝{a，'，'，(，)}，VN={S，L}，S，P)，其中P为， S→(L)|a L→L，S|S 右句型(L，(L，S))的句柄是(28)。
A．(L，(L，S))
B．(L，S)
C．L,S
D．S
正确答案：C
解析：在自底向上分析的过程中，按最右推导的逆过程构造出最右推导，称为规范归约。关键是每步找出被归约的右句型的“可归约串”，称为“句柄”。请读者仔细领会句柄的定义。右句型(最右推导推导出的句型)γ的句柄是一个产生式A→β以及γ中的一个位置，根据这个位置可找到β，用A代替β得到最右推导的前一个右句型。即如果有下面的最右推导：SaAwaβw那么，在a后A→β是aβw的句柄。句柄右边的w仅含终结符号。有的教课书上，句柄的定义借助于短语、直接短语的定义给出：设G＝(VT,VN，S，P)足一个文法，若SaAγaβγ则在句型aβγ中，β是相对于非终结符号A的短语。又若SaAγaβγ则在句型αβγ中，β是相对于非终结符号A的直接短语，最左边的直接短语称为句柄。根据句型(L，(L,S))的最右推导：S(L,(L))(L，(L，S))(此步最右推导使用规则S→L，S)因此，(L，(L,S)中的L,S是句型(L，(L,S))的句柄。 -
第4题：
文法G=(VT，VN，P，S)的类型由G中的(21)决定。若GO=({a，b}，{S，X， Y}，P，S)，P中的产生式及其序号如下：
1：S→XaaY
2：X→YY|b
3：Y→XbX|a
则GO为(22)型文法，对应于(23)，由GO推导出句子aaaa和baabbb时，所用产生式序号组成的序列分别为(24)和(25)。
A．VT
B．VN
C．P
D．S
正确答案：C
-
第5题：
已知文法G2=(VT={a，'，'，(,)}，VN{S,L}，S，P)，其中P为， S→(L)|a L→L，S|S (a，(a，a))是L(G2[S])的句子，这个句子的最左推导是(28)
A．
B．
C．
D．
正确答案：C
解析：设文法G=(VT，VN，S，P)，A→β∈P，γ，δ∈V*，则称γAδ直接推导出γβδ，表示成：γAδγβδ也称γβδ直接归约到γAδ。对于以上公式，若γ∈VT*，即A是γAδ中最左边的非终结符号，则称以上公式是一个最左推导。若Sa的每一步都是最左推导，则称Sa是一个最左推导，a称为一个左句型。对于以上公式，若δ∈VT*，即A是γAδ中最右边的非终结符号，则称以上公式是一个最右推导。若Sa的每一步都是最右推导，则称Sa是一个最右推导，a称为一个右句型。最右推导也称作规范推导，右句型也称作规范句型。对于句子(a，(a，a))，被选择答案中A是最右推导，C是最左推导，B和D的推导序列中，既有最左推导，又有最右推导。