计算理论期末练习题(2015)

A→0A|1A|ε

2）{w|w以相同的符号开始和结束}； S→0A0|1A1 A→0A|1A|ε?

3）{w|w的长度为奇数}。 S→0A|1A A→0B|1B|ε? B→0A|1A

5、利用泵引理证明下述语言不是上下文无关的。 1）{w#t|w,t?{a,b}*,且w是t的子串}；

假设该语言上下文无关，设p为泵长度，取S=0p1p#0p1p, 由泵引理知，S可以划分为uvxyz且满足泵引理条件。显然，v,y中不包含#，不然抽取后的S=uxz中将不含#从而不在该语言中。

子串vxy不能落在#的左侧，否则uv2xy2z中#左侧的字符串长度将大于右边。

子串vxy不能落在#的右侧，否则uxz中#左侧的字符串长度也会大于右边。

现在假设#?x，则必存在不全为0的i,j，使得vy=1i0j，下面分两种情况考虑：

② j≠0, 则uxz=0p1p-i#0p-j1p不在该语言中

②j=0, 则uv2xy2z中#左侧的字符串长度大于右边，不在该语言中。0p 1p-i 1i # 0j 0p-j 1p=uvxyz; 0p 1p-i 12i # 02j 0p-j 1p=uv2xy2z;

2）{t1#t2#?#tk|k?2,ti?{a,b}*,且存在i?j是的ti=tj}。

假设该语言上下文无关，设p为泵长度，取S=apbp#apbp, 由泵引理知，S可以划分为uvxyz且满足泵引理条件。显然，v,y中不包含#，不然抽取后的S=uxz中将不含#从而不在该语言中。

子串vxy不能落在#的左侧，否则uv2xy2z中#左侧的字符串长度将大于右边。

子串vxy不能落在#的右侧，否则uxz中#左侧的字符串长度也会大于右边。

于是vxy跨越#两侧.此时，S经抽取成uxz后，具有apbi#ajbp的形式，其中，i,j不全为p。(亦可为ap bp-i #ap-j bp，只是符号的不同，传达的意思都是p-i不等于p-j，是因为i与j是相等的)

因此，uxz不在该语言中。 综上该语言不是上下文无关的。

6、给出识别语言（01?001?010）*的NFA，将该NFA转化为等价的DFA。

7、已知DFA G如下图所示, 写出CONVERT(G)的结果，要求步骤

8、把下述正则表达式转换成非确定型自动机（NFA）。

a) (0∪1)*000(0∪1)* b) (((00)*(11))∪01)*

9、已知CFG G，如下： E→E＋T|T T→T×E|F F→（E）|a

给出下述字符串的语法分析树和派生。 a. a b. a+a c. a+a+a d. ((a))

10、在下列每个输入串上，给出M所进入的格局序列： a. 0

b. 00 c. 000 d. 000000