12.已知文法G[E]:E→ET+|T T→TF* | F F→F^ | a
试证：FF^^*是文法的句型，指出该句型的短语、简单短语和句柄。 [答案]
该句型对应的语法树如下：
该句型相对于E的短语有FF^^*；相对于T的短语有FF^^*,F;相对于F的短语有F^;F^^;简单短语有F;F^;句柄为F. 13.一个上下文无关文法生成句子abbaa的推导树如下： (1)给出串abbaa最左推导、最右推导。 (2)该文法的产生式集合P可能有哪些元素？ (3)找出该句子的所有短语、直接短语、句柄。
[答案]
(1)串abbaa最左推导:
S=>ABS=>aBS=>aSBBS=>aεBBS=>aεbBS=>aεbbS=>aεbbAa=>aεbbaa 最右推导：
S=>ABS=>ABAa=>ABaa=>ASBBaa=>ASBbaa=>ASbbaa=>Aεbbaa=>aεbbaa (2)产生式有：S→ABS |Aa|ε A→a B→SBB|b
(3)该句子的短语有a1b1b2a2a3、a1、b1、b2、b1b2、a2a3、a2； 直接短语有a1、b1、b2、a2； 句柄是a1。
14.给出生成下列语言的上下文无关文法。
nnmm
(1){ abab |n，m>=0}
nmmn
(2){ 10 10| n，m>=0}
rr
(3){WaW|W属于{0|a}*，W表示W的逆}
[答案]
（1）{abab| n，m>=0} S->AA A->aAb|ε
nmmn
(2) { 10 10| n，m>=0} S->1S0|A A->0A1|ε
r
（3）{WaW|W属于{0|a}*，Wr表示W的逆} S->0S0|1S1|ε
15.给出生成下列语言的三型文法。
n
(1){ a|n >=0 }
nm
(2){ ab|n,m>=1 }
nmk
(3) {abc|n,m,k>=0 } [答案]
(1) { an >=0 }的三型文法为： S->aS|ε
nm
(2){ ab|n,m>=1 }的三型文法为： S->aA A->aA|bB B->bB|ε
nmk
n|nn
mm
(3){abc|n,m,k>=0 }的三型文法为:
A->aA|bB|cC|ε B->bB|cC|ε C->cC|ε 16.构造一文法产生任意长的a,b串，使得 |a|<=|b|<=2|a|
其中，“|a|”表示a字符的个数;“|b|”表示b字符的个数。 [分析]
b的个数在a与2a之间，所以应想到形如aSBS和BSaS的形式，B为1到2个b，即可满足条件。 [答案]
如分析中所述，可得文法如下： S-aSBS|BSaS|ε B->bb|b
第1个产生式为递归定义，由于在第2个产生式中B被定义为1或2个b，所以第1个产生式可以保证b的个数在|a|与2|a|之间，而17.下面的文法产生a的个数和b的个数相等的非空a,b串 S->aB|bA B->bS|aBB|b A->aS|bAA|a
其中非终结符B推出b比a的个数多1个的串，A则反之。 说明该文法是二义的。
对上述文法略作修改，使之非二义，并产生同样的语言。 （略做修改的含义是：不增加非终结符。） [答案]
句子aabbab有两种不同的推导。
S=>aB=>aaBB=>aabB=>aabbS=>aabbaB=>aabbab S=>aB=>aaBB=>aabSB=>aabbAB=>aabbaB=>aabbab 即它可以产生两棵不同的语法树，故它是二义的。
修改后的无二义文法如下：
S->aBS|bAS|aB|bA B->aBB|b A->bAA|a 18.给出0，1，2，3型文法的定义。 [答案]
乔姆斯基(chomsky)把文法分成类型，即0型，1型，2型和3型，0型强于1型，1型强于2型，2型强于3型。
如果它的每个产生式α->β的结构是α∈（VnUVt）*且至少含有一个非终结符,而β∈（VnUVt）*，我们说G=（Vt，Vn，S，δ）是一个
0型文法也称短语文法。一个非常重要的理论结果是，0型文法的能力相当于图灵(Tunring)机。或者说，任何0型语言都是递归可枚举如果把0型文法分别加上以下的第i条限制，则我们就得i型文法为： 1．G的任何产生式α->β 均满足|α|<=|β|；仅仅S->ε例外， 但S不得出现在任何产生式的右部。
2．G的任何产生式为A->β，A∈Vn，β∈（VnUVt）* 3．G的任何产生式为A->aB或A->a，其中A，B∈Vn
1型文法也称上下文有关文法。这种文法意味着，对非终结符进行替换时务必考虑上下文，而且，—般不允许替换成空串。 2型文法对非终结符进行替换时无须考虑上下文， 3型文法也称线性文法。
三
1.构造正规式1(0|1)*101相应的DFA。 先构造NFA
确定化
重新命名，令AB为B、AC为C、ABY为D
DFA：
2.将下图确定化：
[答案]
重新命名，令VQ为A、QU为B、VZ为C、V为D、QUZ为E、Z为F。
DFA：
3.把下图最小化：
答案