当前位置：文档库 › 形式语言与自动机课后习题答案

形式语言与自动机课后习题答案

第二章

4．找出右线性文法，能构成长度为1至5个字符且以字母为首的字符串。

答：G={N,T,P,S}

其中N={S,A,B,C,D} T={x,y} 其中x∈{所有字母} y∈{所有的字符} P如下: S→x S→xA A→y A→yB

B→y B→yC C→y C→yD D→y

6．构造上下文无关文法能够产生

L={ω/ω∈{a,b}*且ω中a的个数是b的两倍}

答：G={N,T,P,S}

其中N={S} T={a,b} P如下:

S→aab S→aba S→baa

S→aabS S→aaSb S→aSab S→Saab

S→abaS S→abSa S→aSba S→Saba

S→baaS S→baSa S→bSaa S→Sbaa

7．找出由下列各组生成式产生的语言（起始符为S）

(1)S→SaS S→b

(2)S→aSb S→c

(3)S→a S→aE E→aS

答：（1）b(ab)n /n≥0}或者L={(ba)n b/n≥0}

(2) L={a n cb n /n≥0}

(3)L={a2n+1 /n≥0}

第三章

1．下列集合是否为正则集，若是正则集写出其正则式。

（1）含有偶数个a和奇数个b的{a,b}*上的字符串集合

（2）含有相同个数a和b的字符串集合

（3）不含子串aba的{a,b}*上的字符串集合

答：（1）是正则集，自动机如下

(2) 不是正则集，用泵浦引理可以证明，具体见17题（2）。

(3) 是正则集

先看L’为包含子串aba的{a,b}*上的字符串集合

显然这是正则集，可以写出表达式和画出自动机。（略）

则不包含子串aba的{a,b}*上的字符串集合L是L’的非。

根据正则集的性质，L也是正则集。

4．对下列文法的生成式，找出其正则式

（1）G=({S,A,B,C,D},{a,b,c,d},P,S),生成式P如下：

S→aA S→B

A→abS A→bB

B→b B→cC

C→D D→bB

D→d

（2）G=({S,A,B,C,D},{a,b,c,d},P,S),生成式P如下：

S→aA S→B

A→cC A→bB

B→bB B→a

C→D C→abB

D→d

答：(1) 由生成式得：

S=aA+B ①

A=abS+bB ②

B=b+cC ③

C=D ④

D=d+bB ⑤

③④⑤式化简消去CD，得到B=b+c(d+bB)

即B=cbB+cd+b =>B=(cb)*(cd+b) ⑥

将②⑥代入①

S=aabS+ab(cb)*(cd+b)+(cb)*(cd+b) =>S=(aab)*(ab+ε)(cb)*(cd+b) (2) 由生成式得：

S=aA+B ①

A=bB+cC ②

B=a+bB ③

C=D+abB ④

D=dB ⑤

由③得 B=b*a ⑥

将⑤⑥代入④ C=d+abb*a=d+ab+a ⑦

将⑥⑦代入② A=b+a+c(d+b+a) ⑧

将⑥⑧代入① S=a(b+a+c(d+ab+a))+b*a

=ab+a+acd+acab+a+b*a

5.为下列正则集，构造右线性文法：

(1){a,b}*

(2)以abb结尾的由a和b组成的所有字符串的集合

(3)以b为首后跟若干个a的字符串的集合

(4)含有两个相继a和两个相继b的由a和b组成的所有字符串集合

答：（1）右线性文法G=({S},{a,b},P,S)

P: S→aS S→bS S→ε

(2) 右线性文法G=({S},{a,b},P,S)

P: S→aS S→bS S→abb

(3) 此正则集为{ba*}

右线性文法G=({S,A},{a,b},P,S)

P: S→bA A→aA A→ε

(4) 此正则集为{{a,b}*aa{a,b}*bb{a,b}*, {a,b}*bb{a,b}*aa{a,b}*}

右线性文法G=({S,A,B,C},{a,b},P,S)

P: S→aS/bS/aaA/bbB

A→aA/bA/bbC

B→aB/bB/aaC

C→aC/bC/ε

7.设正则集为a(ba)*

(1)构造右线性文法

(2)找出（1）中文法的有限自 b动机

答：（1）右线性文法G=({S,A},{a,b},P,S)

P: S→aA A→bS A→ε

（2）自动机如下：

(p2是终结状态)

9.对应图（a）(b)的状态转换图写出正则式。（图略）

（1）由图可知q0=aq0+bq1+a+ε

q1=aq2+bq1

q0=aq0+bq1+a

=>q1=abq1+bq1+aaq0+aa

=(b+ab) q1+aaq0+aa

=(b+ab) *( aaq0+aa)

=>q0=aq0+b(b+ab) *( aaq0+aa ) +a+ε

= q0(a+b (b+ab) *aa)+ b(b+ab) *aa+a+ε

=(a+b (b+ab) *aa) *((b+ab) *aa+a+ε)

=(a+b (b+ab) *aa) *

(3)q0=aq1+bq2+a+b

q1=aq0+bq2+b

q0=aq1+bq0+a

=>q1=aq0+baq1+bbq0+ba+b

=(ba)*(aq0 +bbq0+ba+b)

=>q2=aaq0+abq2+bq0+ab+a

=(ab)*(aaq0 +bq0+ ab+a)

=>q0=a(ba)*(a+bb) q0 + a(ba)*(ba+b)+b(ab)*(aa+b)q0+ b(ab)*(ab+a)+a+b =[a(ba)*(a+bb) +b(ab)*(aa+b)]* (a(ba)*(ba+b)+ b(ab)*(ab+a)+a+b)

10.设字母表T={a,b},找出接受下列语言的DFA：

（1）含有3个连续b的所有字符串集合

（2）以aa为首的所有字符串集合

（3）以aa结尾的所有字符串集合

01202

14构造DFA M1等价于NFA M，NFA M如下：

（1）M=({q0,q1 q2,q3},{a,b},σ,q0,{q3}),其中σ如下：

σ(q0,a)={q0,q1} σ(q0,b)={q0}

σ(q1,a)={q2} σ(q1,b)= {q2 }

σ(q2,a)={q3} σ(q2,b)= Φ

σ(q3,a)={q3} σ(q3,b)= {q3 }

（2）M=({q0,q1 q2,q3},{a,b},σ,q0,{ q1,q2}),其中σ如下：

σ(q0,a)={q1,q2} σ(q0,b)={q1}

σ(q1,a)={q2} σ(q1,b)= {q1,q2 }

σ(q2,a)={q3} σ(q2,b)= {q0}

σ(q3,a)= Φσ(q3,b)= {q0}

答：（1）DFA M1={Q1, {a,b},σ1, [q0],{ [q0,q1,q3]，[q0,q2,q3]，[q0, q1,q2,q3]}

其中Q1={[q0],[q0,q1], [q0,q1,q2],[ q0,q2],[ q0,q1, q2,q3],[ q0,q1, q3],[ q0,q2, q3],[ q0,q3]}

（2）DFA M1={Q1, {a,b},σ1, [q0],{ [q1],[q3], [q1,q3],[q0,q1,q2],[q1,q2] ,[q1,q2,q3],[q2,q3]}

其中Q1 ={[q0],[q1,q3], [q1],[q2],[ q0,q1,q2],[q1,q2],[q3], [q1,q2,q3],[q2,q3]} 1

(2)将此ε-NFA转换为没有ε的NFA

答：（1）可被接受的的串共 23个，分别为aac, abc, acc, bac, bbc, bcc, cac, cbc, ccc, caa, cab, cba, cbb, cca, ccb, bba, aca, acb, bca, bcb, bab, bbb, abb （2）ε-NFA：M=({p,q,r},{a,b,c},σ,p,r) 其中σ如表格所示。

因为ε-closure(p)= Φ

则设不含ε的NFA M1=({p,q,r},{a,b,c},σ1,p,r)

σ1(p,a)=σ’(p,a)=ε-closure(σ(σ’(p,ε),a))={p}

σ1(p,b)=σ’(p,b)=ε-closure(σ(σ’(p,ε),b))={p,q}

σ1(p,c)=σ’(p,c)=ε-closure(σ(σ’(p,ε),c))={p,q,r}

σ1(q,a)=σ’(q,a)=ε-closure(σ(σ’(q,ε),a))={p,q}

σ1(q,b)=σ’(q,b)=ε-closure(σ(σ’(q,ε),b))={p,q,r}

σ1(q,c)=σ’(q,c)=ε-closure(σ(σ’(q,ε),c))={p,q,r}

σ1(r,a)=σ’(r,a)=ε-closure(σ(σ’(r,ε),a))={p,q,r}

σ1(r,b)=σ’(r,b)=ε-closure(σ(σ’(r,ε),b))={p,q,r}

σ1(r,c)=σ’(r,c)=ε-closure(σ(σ’(r,ε),c))={p,q,r}

图示如下：(r为终止状态)

16．设NFA M=({q0,q1},{a,b},σ,q0,{q1}),其中σ如下：

σ(q0,a)={q0,q1} σ(q0,b)={q1}

σ(q1,a)= Φσ(q1,b)= {q0, q1}

构造相应的DFA M1，并进行化简

答：构造一个相应的DFA M1={Q1, {a,b},σ1, [q0],{ [q1]，[q0,q1]}

其中Q1 ={[q0]，[q1]，[q0,q1]}

17.使用泵浦引理，证明下列集合不是正则集：

（1）由文法G的生成式S→aSbS/c产生的语言L(G)

（2）{ω/ω∈{a,b}*且ω有相同个数的a和b}

（3）{a k ca k/k≥1}

（4）{ωω/ω∈{a,b}*}

证明：（1）在L(G)中，a的个数与b的个数相等

假设L(G)是正则集，对于足够大的k取ω= a k (cb)k c

令ω=ω1ω0ω2

因为|ω0|>0 |ω1ω0|≤k 存在ω0使ω1ω0iω2∈L

所以对于任意ω0只能取ω0=a n n∈(0,k)

则ω1ω0iω2= a k–n(a n)i(cb)k c 在i不等于0时不属于L

与假设矛盾。则L(G)不是正则集

（2）假设该集合是正则集，对于足够大的k取ω= a k b k

令ω=ω1ω0ω2

因为|ω0|>0 |ω1ω0|≤k 存在ω0使ω1ω0iω2∈L

所以对于任意ω0只能取ω0=a n n∈(0,k)

则ω1ω0iω2= a k–n(a n)i b k在i不等于0时a与b的个数不同，不属于该集合与假设矛盾。则该集合不是正则集

（3）假设该集合是正则集，对于足够大的k取ω= a k ca k

令ω=ω1ω0ω2

因为|ω0|>0 |ω1ω0|≤k 存在ω0使ω1ω0i ω2∈L 所以对于任意ω0只能取ω0=a n n ∈(0,k)

则ω1ω0i ω2= a k –n (a n )i ca k

在i 不等于0时c 前后a 的个数不同，不属于该集合与假设矛盾。则该集合不是正则集

（4）假设该集合是正则集，对于足够大的k 取ωω= a k ba k b 令ωω=ω1ω0ω2

因为|ω0|>0 |ω1ω0|≤k 存在ω0使ω1ω0i ω2∈L 所以对于任意ω0只能取ω0=a n n ∈(0,k)

则ω1ω0i ω2= a k –n (a n )i ba k b 在i 不等于0时不满足ωω的形式，不属于该集合与假设矛盾。则该集合不是正则集

18．构造米兰机和摩尔机

对于{a,b}*的字符串，如果输入以bab 结尾，则输出1；如果输入以bba 结尾，则输出2；否则输出3。答：米兰机：

说明状态qaa 表示到这个状态时，输入的字符串是以aa 结尾。其他同理。

a/3

b/3

a/3 a/3 b/3

b/1

a/2 b/3

摩尔机，状态说明同米兰机。

a a

b a

a b a b

a b

b b

第四章

10. 把下列文法变换为无ε生成式、无单生成式和没有无用符号的等价文法：

qaa

qba qbb

qab qaa,3 b/3 qbba,2

qbb,3 b/3

qbab,1 b/3 qaba,3

b/3

qaab,3 b/3

S →A1 | A2 , A1→A3 | A4 , A2→A4 | A5 , A3→S | b |ε, A4→S | a，A5→S | d |ε

解: ⑴由算法3，变换为无ε生成式：

N’ = { S, A1,A2,A3,A4,A5 }

G1 = ( { S1,S, A1,A2,A3,A4,A5 } , { a,b,d }, P1 , S1 ) ,其中生成式P1如下：S1→ε| S ,

S →A1 | A2 ,

A1→A3 | A4 ,

A2→A4 | A5 ,

A3→S | b ,

A4→S | a ,

A5→S | d ,

⑵由算法4，消单生成式：

N S1 = { S1,S,A1,A2,A3,A4, A5 } ,

N S = N A1 = N A2 = N A3 = N A4 = N A5 = { S, A1,A2,A3,A4, A5 } ,

运用算法4，则P1变为：

S1 →a | b | d |ε ,

S →a | b | d ,

A1→a | b | d ,

A2→a | b | d ,

A3→a | b | d ,

A4→a | b | d ,

A5→a | b | d

⑶由算法1和算法2，消除无用符号，得到符合题目要求的等价文法：

G1 = ( { S1 } , { a,b,d } , P1 , S1 ) ，其中生成式P1为：S1→a | b | d |ε.

11.设2型文法G = ( { S,A,B,C,D,E,F } , { a,b,c } , P , S ) , 其中P：

S →ASB |ε; A →aAS | a ; B →SBS | A | bb

试将G变换为无ε生成式,无单生成式,没有无用符号的文法,再将其转换为Chomsky范式.

解: ⑴由算法3，变换为无ε生成式：

N’ = { S }

由S →ASB得出S →ASB | AB ,

由A →aAS得出A →aAS | aA ,

由B →SBS得出B →SBS | SB | BS |B,

由S∈N’得出S1→ε| S ,

因此无ε的等效文法G1 = ( { S1,S,A,B } , { a,b,d } , P1 , S1 ) ,其中生成式P1如下：

S1→ε| S ,

S →ASB | AB ,

A →aAS | aA | a,

B →SBS | SB | BS | B| A | bb ,

⑵由算法4，消单生成式：

N S1 = { S1,S } , N S = { S } , N A = { A } , N B = { A,B }

由于S →ASB | AB∈P且不是单生成式,故P1中有S1→ε| ASB | AB ,

同理有 S →ASB | AB , A →aAS | aA | a , B →SBS | SB | BS | aAS | aA | a | bb,

因此生成的无单生成式等效文法为

G1 = ( { S1,S, A,B } , { a,b } , P1 , S1 ) ,其中生成式P1如下：

S1→ε| ASB | AB ,

S →ASB | AB ,

A →aAS | aA | a ,

B →SBS | SB | BS | aAS | aA | a | bb,

⑶由算法1和算法2，消除无用符号(此题没有无用符号);

⑷转化为等价的Chomsky范式的文法:

将S1 →ASB变换为 S →AC , C →SB ,

将S →ASB 变换为 S →AC ,

将A →aAS | aA 变换为 A →ED | EA, D →AS , E →a,

将B →SBS | aAS | aA | a | bb , 变换为 B →CS | ED | EA | FF, F →b ,

⑸由此得出符合题目要求的等价文法：

G1 = ( { S1,S, A,B,C,D } , { a,b } , P1 , S1 ) ,其中生成式P1如下：

S1→ε| AC | AB ,

S →AC | AB ,

A →ED | EA | a ,

B →CS | SB | BS | ED | EA | a | FF ,

C →SB ,

D →AS ,

E →a ,

F →b .

15.将下列文法变换为等价的Greibach范式文法:

⑴S →DD | a , D →SS | b

解: 将非终结符排序为S,D,S为低位,D为高位,

⑴对于D →SS ,用S →DD | a 代入得 D →DDS | aS | b ,

用引理变化为D →aS | b | aSD' | bD' , D’→DS | DSD’ ,

⑵将D生成式代入S生成式得 S →aSD | bD | aSD’D | bD'D | a ,

⑶将D生成式代入D’生成式得

⑷由此得出等价的Greibach范式文法：

G1 = ( { S,D,D’ } , { a,b } , P1 , S ) ,其中生成式P1如下：

S →aSD | bD | aSD’D | bD'D | a ,

D →aS | b | aSD' | bD' ,

⑵A1→A3b | A2a , A2→A1b | A2A2a | b , A3→A1a | A3A3b | a

解: ⑴转化为等价的Chomsky范式的文法:

A1→A3A4 | A2A5 ,

A2→A1A4 | A2A6 | b ,

A3→A1A5 | A3A7 | a ,

A4→b ,

A5→a ,

A6→A2A5 ,

A7→A3A4 ,

⑵转化为等价的Greibach范式的文法:

将非终结符排序为A1, A2,A3,A4,A5 ,A1为低位A5为高位,

①对于A2→A1A4 ,用A1→A3A4 | A2A5代入得A2→A3A4A4 | A2 A5A4 | A2A6 | b ,

用引理变化为

A2→A3A4A4 | b | A3A4A4A2’ | bA2’ ,

A2’→A5A4A2’ | A6A2’ | A5A4 | A6 ,

②对于A3→A1A5 ,用A1→A3A4 | A2A5代入得A3→A3A4A5 | A2A5A5 | A3A7 | a ,

A3’→A4A5| A4A4A5A5| A4A4A2’A5A5| A7| A4A5A3’| A4A4A5A5A3’| A4A4A2’A5A5A3’| A7A3’ ,

③对于A6→A2A5 ,将A2生成式代入A6生成式得

A6→A3A4A4A5 | bA5 | A3A4A4A2’A5 | bA2’A5 ,

④对于A7→A3A4 , 将A3生成式代入A7生成式得

⑤将A5,A6生成式代入A2’生成式得

⑶由此得出等价的Greibach范式文法:

G1 = ( { S,D,D’ } , { a,b } , P1 , S ) ,其中生成式P1如下：

A1→A3A4 | A2A5 ,

A2→A3A4A4 | b | A3A4A4A2’ | bA2’ ,

A4→b ,

A5→a ,

A6→bA5A5A4A4A5| bA2’A5A5A4A4A5| aA4A4A5| bA5A5A3’A4A4A5| bA2’A5A5A3’A4A4A5

20.设文法G有如下得生成式: S →aDD , D →aS | bS | a , 构造等价的下推自动机.解: 根据P162-163的算法,构造下推自动机M,使M按文法G的最左推导方式工作.

设M = (Q,T,Г,δ,q0,Z0,F ),其中

Q = { q0,q f } ,

T = { a,b} ,

Г = { a,b,D,S } ,

Z0 = S ,

F = { q f } ,

δ定义如下:

δ( q0,ε,S) = { ( q0, aDD ) } ,

δ( q0,ε,D ) = { ( q0,aS ) , ( q0,bS ) , ( q0,a ) } ,

δ( q0,a,a ) = { ( q0,ε ) } ,

δ( q0,ε,ε ) = { ( q f,ε ) } .

21.给出产生语言 L = { a i b j c k | i , j , k≥0 且 i = j 或者 j = k }的上下文无关

文法.你给出的文法是否具有二义性?为什么?

解: G=({S,A,B,C,D,E},{a,b,c}，P，S)

因为当句子ω中a,b,c个数相同时，对于ω存在两个不同的最左(右)推导。

如abc L，存在两个不同的最左推导S AD aAbD abD abcC abc 及S EB aEB aB abBc abc 。

22.设下推自动机 M = ( {q0,q1},{a,b},{Z0,X},δ, q0, Z0,φ),其中δ如下:

δ(q0,b, Z0) = {(q0, XZ0)} ,δ(q0,ε, Z0) = {(q0, ε)} ,A

δ(q0,b, X) = {(q0, XX)} , δ(q1,b, X) = {(q1, ε)} ,

δ(q0,b, X) = {(q1, X)} , δ(q1,a, Z0) = {(q0, Z0)} ,

试构造文法G产生的语言 L (G) = L(M).

解: 在G中,N = { [q0,Z0,q0], [q0,Z0,q1], [q0,X,q0], [q0,X,q1], [q1,Z0,q0], [q1,Z0,q1], [q1,X,q0], [q1,X,q1] } .

⑴S生成式有

S →[q0,Z0,q0] ,

S →[q0,Z0,q1] ,

根据δ(q0,b, Z0) = {(q0, XZ0)} ,则有

[q0,Z0,q0] →b[q0,X,q0] [q0,Z0,q0] ,

[q0,Z0,q0] →b[q0,X,q1] [q1,Z0,q0] ,

[q0,Z0,q1] →b[q0,X,q0] [q0,Z0,q1] ,

[q0,Z0,q1] →b[q0,X,q1] [q1,Z0,q1] ,

因为有δ(q0,b, X) = {(q0, XX)},则有

[q0,X,q0] →b[q0,X,q0] [q0,X,q0] ,

[q0, X,q0] →b[q0,X,q1] [q1, X,q0] ,

[q0, X,q1] →b[q0,X,q0] [q0, X,q1] ,

[q0, X,q1] →b[q0,X,q1] [q1, X,q1] ,

因为有δ(q0,a, X) = {(q1, X)},则有

[q0,X,q0] →a[q1,X,q0] ,

[q0,X,q1] →a[q1,X,q1] ,

因为有δ(q1,a, Z0) = {(q0, Z0)},则有

[q1,Z0,q0] →a[q0,Z0,q0] ,

[q1,Z0,q1] →a[q0,Z0,q1] ,

因为有δ(q0,ε, Z0) = {(q0, ε)},则有

[q0,Z0,q0] →ε,

因为有δ(q1,b, X) = {(q1, ε)},则有

[q1,X,q1] →ε

⑵利用算法1和算法2,消除无用符号后,得出文法G产生的语言L(G) = { N,T,P,S }

其中N = { S,[q0,Z0,q0],[q1,Z0,q0],[q1,X,q1], [q0,X,q1] },T = { a,b },生成式P如下:

S →[q0,Z0,q0] ,

[q0,Z0,q0] →b[q0,X,q1] [q1,Z0,q0] ,

[q0, X,q1] →b[q0,X,q1] [q1, X,q1] ,

[q0,X,q1] →a[q1,X,q1] ,

[q1,Z0,q0] →a[q0,Z0,q0] ,

[q0,Z0,q0] →ε,

[q0,Z0,q0] →ε.

23.证明下列语言不是上下文无关语言:

⑴{ a n b n c m | m≤n };

证明: 假设L是上下文无关语言,由泵浦引理,取常数p,当ω∈L且|ω|≥p时,可取ω = a p b p c p ,将ω写为ω=ω1ω2ω0ω3ω4 ,同时满足|ω2ω0ω3|≤p

⑴ω2和ω3不可能同时分别包含a和c,因为在这种情况下,有|ω2ω0ω3|>p;

⑵如果ω2和ω3都只包含a (b) ,即ω2ω0ω3 = a j (b j ) (j≤p) ,则当i≠1时, ω1ω2iω0ω3iω4中会出现a的个数与b的个数不等;

如果ω2和ω3都只包含c ,即ω2ω0ω3 = c j (j≤p),当i大于1时,ω1ω2iω0ω

3iω

4中会出现c的个数大于a的个数 (b的个数);

⑶如果ω2和ω3分别包含a和b (b和c) ,当i=0时ω1ω2iω0ω3iω4中会出

现a, b的个数小于c的个数（或a,b个数不等）

这些与假设矛盾,故L不是上下文无关语言.

⑵{ a k | k是质数 };

证明: 假设L是上下文无关语言,由泵浦引理,取常数p,当ω∈L且|ω|≥p时,可取ω=a k ( k≥p且k≠1 ) ,将ω写为ω=ω1ω2ω0ω3ω4 ,同时满足|ω2ω0ω3|≤p ,

且

|ω2ω3|=j≥1 ,则当i=k+1时,|ω1ω2iω0ω3iω4|=k+(i-1)*j=k+k*j= k*(1+j) ,k*(1+j)至少包含因子k且k≠1 ,因此必定不是质数,即ω1ω2iω0ω

3iω

4不属于L.

这与假设矛盾,故L不是上下文无关语言.

⑶由 a,b,c 组成的字符串且是含有 a,b,c 的个数相同的所有字符串.

证明: 假设L是上下文无关语言,由泵浦引理,取常数p,当ω∈L且|ω|≥p时,可取ω = a k b k c k (k≥p) ,将ω写为ω=ω1ω2ω0ω3ω4 ,同时满足|ω2ω0ω3|≤p

⑴ω2和ω3不可能同时分别包含a和c,因为在这种情况下,有|ω2ω0ω3|>p;

⑵如果ω2和ω3都只包含a (b或c) ,即ω2ω0ω3 = a j (b j或c j ) (j≤p) ,

则当i≠1时, ω1ω2iω0ω3iω4中会出现a,b,c的个数不再相等;

⑶如果ω2和ω3分别包含a和b (b和c) , ω1ω2iω0ω3iω4中会出现a,b的

个数与c的不等;

这些与假设矛盾,故L不是上下文无关语言.

24.设G是Chomsky 范式文法,存在ω∈ L (G) ，求在边缘为ω的推导树中,最长的路

径长度与ω的长度之间的关系.

解: 设边缘为ω的推导树中,最长路径长度为n,则它与ω的长度之间的关系为|ω|≤2n-1 .

因为由Chomsky范式的定义可知,Chomsky范式文法的推导树都是二叉树,在最长路径长度为n的二叉推导树中,满二叉树推出的句子长度最长,为2n-1,因此ω的长度与其推导树的最长路径长度n的关系可以用上式表示.

25.设计PDA接受下列语言(注意:不要求为确定的)

⑴{ 0m1n | m≤n };

解: 设PDA M = ( Q,T,Г,δ,q0,Z0,F ),其中

Q = { q0,q1,q f } ,

T = { 0,1} ,

Г = { 0,1, Z0 } ,

F = { q f } ,

δ定义如下:

δ( q0, ε, Z0 ) = { ( q1, Z0 ) } ,

δ( q0,0, Z0 ) = { ( q0, 0Z0 ) } ,

δ( q0,0,0 ) = { ( q0, 00 ) } ,

δ( q0,1, Z0 ) = { ( q f,ε ) } ,

δ( q0,1, 0 ) = { ( q1,ε ) } ,

δ( q1,1, 0 ) = { ( q1,ε ) } ,

δ( q1,ε, Z0 ) = { ( q f,ε ) }

δ( q1,1, Z0 ) = { ( q f,ε ) }

δ( q f,1, ε) = { ( q f,ε ) }

⑵{ 0m1n | m≥n };

解: 设PDA M = ( Q,T,Г,δ,q0,Z0,F ),其中

Q = { q0,q1,q f } ,

T = { 0,1} ,

Г = { 0,1, Z0 } ,

F = { q f } ,

δ定义如下:

δ( q0, ε, Z0 ) = { ( q1, Z0 ) } ,

δ( q0,0, Z0 ) = { ( q0, 0Z0 ) } ,

δ( q0,0,0 ) = { ( q0, 00 ) } ,

δ( q0,1, 0 ) = { ( q1,ε ) } ,

δ( q1,1, 0 ) = { ( q1,ε ) } ,

δ( q1,ε,Z0 ) = { ( q f,ε ) } ,

δ( q1,ε,0 ) = { ( q f,ε ) }

δ( q f,1, ε) = { ( q f,ε ) }

⑶{ 0m1n0m | n和m任意 };

解: 设PDA M = ( Q,T,Г,δ,q0,Z0,F ),其中

Q = { q0,q1, q2,q3,q f } ,

T = { 0,1} ,

Г = { 0,1, Z0 } ,

F = { q f } ,

δ定义如下:

δ( q0,0, Z0 ) = { ( q0, 0Z0 ) } ,

δ( q0,0,0 ) = { ( q0, 00 ),( q0,ε)} ,

δ( q0,1, Z0 ) = { ( q3,ε ) } ,

δ( q3,1, ε) = { (q3,ε) } ,

δ( q3,ε, ε) = { ( q f,ε ) } ,

δ( q0,1,0 ) = { ( q1,0 ) } ,

δ( q1,1,0 ) = { ( q1,0 ) } ,

δ( q1,0,0 ) = { ( q2,ε ) } ,

δ( q2,0,0 ) = { ( q2,ε ) } ,

δ( q2,ε, Z0 ) = { ( q f,ε ) } ,

δ( q0, ε, Z0 ) = { ( q f, ε)}nm

第五章

1.考虑如下的图灵机 M = ( {q0, q1, q f, },{0,1},{0,1,B},δ, q0,B,{ q f } ),其中

δ定义为:

δ(q0,0) = {(q1,1,R)} , δ(q1,1) = {(q0,0,R)} , δ(q1,B) = {(q f,B,R)} ,非形式化但准确地描述该图灵机的工作过程及其所接受的语言.

解: 开始时,M的带上从左端起放有字符串0(10)i(i≥0),后跟无限多个空白符的第一次动作先读到第一个0,并改写为1;然后右移,如果找到第一个1,则改写为0,并继续向右寻找下一个0,这样重复进行.当向右寻找1的时候,找到一个空白符B,则结束.

该图灵机所接受的语言L(M) = { 0(10)i | i≥

形式语言与自动机

形式语言与自动机的发展和在计算理论中的作用 2015060104020王桢形式语言是语言学衍生过来的，开始形式语言并没有用于研究计算机编程语言，而只是研究自然语言的结构。在电子计算机出现以后，人们就马上想到用计算机来作自然语言的机械翻译。可是这项工作并没有所成果，对自然语言的结构理解太片面化，翻译质量不理想也很难提高。1956年，乔姆斯基发表了用形式语言方法研究自然语言的第一篇文章。他对语言进行定义：给定一组符号，称为字母表，用∑表示。又用∑*表示∑中字母组成的所有符号串的集合。∑*的每个子集都是∑上的一个语言。乔姆斯基的语言定义方法为人们所公认，一直沿用下来，乔姆斯基根据文法将语言分成3大类。同时克林在研究神经细跑中，建立了识别语言的系统有穷状态自动机。乔姆斯基发现自动机和文法分别从生成和识别去表达语言，并建立了形式文法和自动机之间的联系，证明语言的形式文法与自动机之间存在着如下的对应关系：①若某一语言能用图灵机来识别，则它就能用O型文法生成，反之亦然；②若某一语言能用线性有界自动机来识别，则它就能用上下文敏感文法生成，反之亦然；③若某一语言能用后进先出自动机来识别，则它就能用上下文自由文法生成，反之亦然；④若某一语言能用有限自动机来识别，则它就能用有限状态文法生成，反之亦然。这一成果将形式语言引入数学，使得形式语言真正诞生。1960年，算法语言ALGOL60报告发表。1961年，又发表了ALGOL60修改报告。在这两个报告中，第一次使用一种称为BNF 范式的形式方法来描述程序设计语言ALGOL60的语法。不久，人们即发现BNF 范式极其类似于形式语言理论中的上下文无关文法，从而打开了形式语言广泛应用于程序设计语言的局面，并给形式语言理论本身的研究以极大的推动，使它发展成为理论计算机科学的一个重要分支。形式语言理论是从语言学衍生而来，作为一种理解自然语言的句法规律。在发展过程中人们发现其在计算机语言中的作用，计算机语言在计算机科学中，形式语言通常作为定义编程语言和语法的基础。对编程语言编译，使之转换成机器语言，形式语言在这一工作中有很重要的作用。形式语言推动了计算机学科的发展，并成为计算机学科里重要的分支。 19世纪中，布尔用数学方法研究思维规律的问题建立了逻辑代数，即布尔代数。肖斯塔科夫和仙农，独立地应用布尔代数于继电器接点电路的分析和综合,

《形式语言与自动机》(王柏、杨娟编著)课后习题答案

形式语言与自动机课后习题答案第二章 4．找出右线性文法，能构成长度为1至5个字符且以字母为首的字符串。答：G={N,T,P,S} 其中N={S,A,B,C,D} T={x,y} 其中x ∈{所有字母} y ∈{所有的字符} P 如下: S →x S →xA A →y A →yB B →y B →y C C →y C →y D D →y 6．构造上下文无关文法能够产生 L={ω/ω∈{a,b}*且ω中a 的个数是b 的两倍} ! 答：G={N,T,P,S} 其中N={S} T={a,b} P 如下: S →aab S →aba S →baa S →aabS S →aaSb S →aSab S →Saab S →abaS S →abSa S →aSba S →Saba S →baaS S →baSa S →bSaa S →Sbaa 7．找出由下列各组生成式产生的语言（起始符为S ） (1) S →SaS S →b (2) S →aSb S →c (3) / (4) S →a S →aE E →aS 答：（1）b(ab)n /n ≥0}或者L={(ba)n b /n ≥0} (2) L={a n cb n /n ≥0} (3) L={a 2n+1 /n ≥0} 第三章 1．下列集合是否为正则集，若是正则集写出其正则式。（1）含有偶数个a 和奇数个b 的{a,b}*上的字符串集合（2）含有相同个数a 和b 的字符串集合（3） < （4）不含子串aba 的{a,b}*上的字符串集合答：（1）是正则集，自动机如下 a

a (2) 不是正则集，用泵浦引理可以证明，具体见17题（2）。 (3) 是正则集先看L’为包含子串aba的{a,b}*上的字符串集合 { 显然这是正则集，可以写出表达式和画出自动机。（略）则不包含子串aba的{a,b}*上的字符串集合L是L’的非。根据正则集的性质，L也是正则集。 4．对下列文法的生成式，找出其正则式（1）G=({S,A,B,C,D},{a,b,c,d},P,S),生成式P如下： S→aA S→B A→abS A→bB B→b B→cC C→D D→bB … D→d （2）G=({S,A,B,C,D},{a,b,c,d},P,S),生成式P如下： S→aA S→B A→cC A→bB B→bB B→a C→D C→abB D→d 答：(1) 由生成式得： S=aA+B ① A=abS+bB ② ] B=b+cC ③ C=D ④ D=d+bB ⑤ ③④⑤式化简消去CD，得到B=b+c(d+bB) 即B=cbB+cd+b =>B=(cb)*(cd+b) ⑥ 将②⑥代入① S=aabS+ab(cb)*(cd+b)+(cb)*(cd+b) =>S=(aab)*(ab+ε)(cb)*(cd+b) (2) 由生成式得： S=aA+B ① A=bB+cC ② … B=a+bB ③ C=D+abB ④ D=dB ⑤ 由③得B=b*a ⑥

形式语言与自动机理论试题答案解析

形式语言与自动机理论试题答案解析一、按要求完成下列填空 1.给出集合{Φ,{Φ}}和集合{ε,0,00}的幂集（2x4'） (1) {Φ,{Φ},{{Φ}},{Φ,{Φ}}} (2) {Φ,{ε},{0},{00},{ε,0},{ε,00},{0,00},{ε,0,00}} 2.设∑={0,1},请给出∑上的下列语言的文法（2x5'） (1)所有包含子串01011的串 S→X01011Y X→ε|0X|1X Y→ε|0Y|1Y (2)所有既没有一对连续的0，也没有一对连续的1的串 A→ε|A’|A” A’→0|01|01A’ A”→1|10|10A” 3.构造识别下列语言的DFA 2x6' (1) {x|x∈{0，1}+且x以0开头以1结尾} （设置陷阱状态，当第一个字符为1时，进入陷阱状态） (2) {x|x∈{0，1}+且x的第十个字符为1} （设置一个陷阱状态，一旦发现x的第十个字符为0，进入陷阱状态）

二、判断（正确的写T ，错误的写F ） 5x2' 1.设1R 和2R 是集合{a,b,c,d,e}上的二元关系，则 3231321)(R R R R R R R I I ? ( T ) 任取(x.,y),其中x,y },,,,{e d c b a ∈，使得321)(),(R R R y x I ∈。 )),(),((321R y z R R z x z ∈∧∈??I },,,,{e d c b a z ∈ )),(),(),((321R y z R z x R z x z ∈∧∈∧∈?? )),(),(()),(),((3231R y z R z x z R y z R z x z ∈∧∈?∧∈∧∈?? 3231),(),(R R y x R R y x ∈∧∈? 3231),(R R R R y x I ∈? 2.对于任一非空集合A ，Φ?A 2 ( T ) 3.文法G ：S A|AS A a|b|c|d|e|f|g 是RG ( F ) 4.3型语言 I 2型语言 I 1型语言 I 0型语言 ( F ) 5.s （rs+s ）*r=rr *s （rr *s ）* ( F ) 不成立，假设r,s 分别是表示语言R ，S 的正则表达式，例如当R={0}，S={1}, L(s(rs+s)*r)是以1开头的字符串，而L(rr*s(rr*s)*)是以0开头的字符串.L(s(rs+s)*r) ≠ L(rr*s(rr*s)*) 所以s(rs+s)*r ≠ rr*s(rr*s)*,结论不成立三、设文法G 的产生式集如下，试给出句子aaabbbccc 的至少两个不同的推导（12分）。 aSBC aBC S |→ ab aB → bB →bb CB →BC bC →bc cC →cc

编译原理论文

对编译原理学习的浅谈专业：******* 学号：********** 姓名：*** 大三半学期过去了，无时不刻感觉到时间真的过得好快，发现它是那么的残忍，从来不给你任何驻足的机会。回首这学期对编译原理的学习，下面简单谈谈我对这门课学习的理解。通过这一学期的学习，我们知道了概括。编译原理课程主要介绍的事编译器构造的一般原理、基本设计方法和主要实现技术。编译原理课程通过编译器的各个组成部分来解释高级语言编写的源程序如何翻译成计算机能够执行的机器语言。这个翻译的过程涉及程序设计语言、机器结构、形式语言理论、类型论、算法和软件工程等方面的知识。例如，对软件工程来说，编译程序是一个很好的实例，编译原理课程所介绍的概念和技术可以用到一般的软件设计中。编译原理的学习对我们有很大的帮助。首先：通过编译原理的学习，有助于大家快速理解、定位和解决在程序编译、测试与运行中出现的问题。另外，编译原理的学习对熟悉编译过程、掌握计算机高级语言的生成机制、理解具体程序的运行状态起着关键作用。在学习的过程中，很多同学认为我们今后的工作不会涉及到编译原理的理论和技术，编译原理没有实际的用处，学习起来就非常的枯燥无味，因此对这门课没有足够的认识。其实这是对编译原理的一种错误认识。该课程中的原理除了可以用于分析编译器以外，还对诸如人工智能、并行处理技术等课程的学习具有指导作用。与此同时编译原理课程可以帮助哦我我们更进一步地理解和综合应用离散数学、高级语言、数据结构、汇编语言等专业基础课程的知识。例如，编译程序应用了多种数据结构，在词法分析阶段使用状态转换图来识别各种单词；在语法分析中使用语法树等来进行语法分析；在存储分配时使用栈式结构和堆式结构进行存储空间的分配。本门课程学习对其它课程的学习和今后很多领域的理论研究具有深远的意义。我觉得要想学好编译原理这门课，一定要做到以下两点，达到知识的融会贯通。对以后学习其他知识打下基础，同时对以前的一些知识有更深的认识。第一：.整体把握一条主线，领会每个阶段的精髓，各个击破。编译器（编译程序）可以分为词法分析、语法分析、语义分析、中间代码生成，代码优化和目标代码生成这六个阶段，每个阶段还会伴有符号表管理和出错管理。在第一章编译器概述中就把编译器化分成这六个阶段，同时还简要的描述了这六个阶段各自的任务，这是贯穿整个课程的一个主线，整个课程就是按这六个阶段组织进行的。所以一开始我们如果能够把握住这条主线，对课程有一个总体的把握，理解编译的过程，然后学习起来也会感觉到比较轻松。当我们从整体上理解编译器的结构之后，然后分章节对各个部分进行细致地阅读理解。按照编译过程的划分，把课程分为六章内容，每章都有它的精髓所在，只要掌握了每章的精髓，就能掌握编译的整个过程。词法分析的精髓主要是词法分析的构造、有限自动机理论的应用；语法分析的精髓主要是语法分析的两种方法——自上而下分析法和自下而上分析法；语义分析主要是属性文法、语法制导定义以及翻译方案；中间代码主要

形式语言与自动机理论蒋宗礼第三章参考答案

第三章作业答案 1．已知DFA M1与M2如图3－18所示。 (敖雪峰 02282068) (1) 请分别给出它们在处理字符串1011001的过程中经过的状态序列。 (2) 请给出它们的形式描述。 S q q 1 图3－18 两个不同的DFA 解答：(1)M1在处理1011001的过程中经过的状态序列为q 0q 3q 1q 3q 2q 3q 1q 3; M2在处理1011001的过程中经过的状态序列为q 0q 2q 3q 1q 3q 2q 3q 1; (2)考虑到用形式语言表示,用自然语言似乎不是那么容易,所以用图上作业法把它们用正则表达式来描述: M1: [01+(00+1)(11+0)][11+(10+0)(11+0)]* M2: (01+1+000){(01)*+[(001+11)(01+1+000)]*} ******************************************************************************* 2．构造下列语言的DFA ( 陶文婧 02282085 ) （1）{0，1}* ，1 （2）{0 ，1}+ ，1 （3）{x|x {0，1}+且x 中不含00的串} （设置一个陷阱状态，一旦发现有00的子串，就进入陷阱状态）

（4）{ x|x∈{0，1}*且x中不含00的串} （可接受空字符串，所以初始状态也是接受状态）（5）{x|x∈{0，1}+且x中含形如10110的子串} （6）{x|x∈{0，1}+且x中不含形如10110的子串} （设置一个陷阱状态，一旦发现有00的子串，就进入陷阱状态）（7）{x|x∈{0，1}+且当把x看成二进制时，x模5和3同余，要求当x为0时，|x|=1,且x≠0时，x的首字符为1 } 1.以0开头的串不被接受，故设置陷阱状态，当DFA在启动状态读入的符号为0，则进入陷阱状态 2.设置7个状态：开始状态q s,q0:除以5余0的等价类，q1：除以5余1的等价类,q2:除以5 余2的等价类，q3:除以5余3的等价类，q4:除以5余4的等价类，接受状态q t

计算机专业导论论文

计算机专业导论学生学院____计算机学院_______ 专业班级____ _____ 学号____ _______学生姓名______ _________ 成绩_____________________ 2013年11月30日

专业导论（论文）在当今世界，几乎所有专业都与计算机息息相关。所以计算机的发明无疑是20世纪最卓越的成就之一。时至今日，计算计的广泛应用极大的促进了生产力的发展，它在当今信息化的社会中已经成为必不可少的工具。我对计算机及计算机学科体系的理解实际上，计算机是一种能够按照事先存储的程序，自动、高速地对数据进行输入、处理、输出和储存的系统。计算机科学是对计算机进行学术研究的传统称谓。主要研究计算技术和执行特定任务的高效算法。该门学科为我们解决确定一个问题在计算机领域内是否可解，如可解其效率如何，以及如何作成更加高效率的程序。时至今日，在计算机科学内已经衍生了许多分支，每一个分支都针对不同类别的问题进行深入研究。计算机工程学是电子工程的一个分支，主要研究计算机软硬件和二者间的彼此联系。软件工程学着重于研究开发高质量软件系统的方法学和实践方式，并试图压缩并预测开发成本及开发周期。信息系统，在一个广泛的有组织环境（商业为主）中的计算机应用。

计算机系统一个计算机系统包括硬件和软件两大部分。硬件是由电子的、磁性的、机械的器件组成的物理实体，包括运算器、存储器、控制器、输入设备与输出设备等5个基本组成部分。软件则是程序和有关文档的总称，包括系统软件、应用软件和工具软件三类。硬件系统的五个部分中控制器是指挥计算机的各个部件按照指令的功能要求协调工作的部件，是计算机的“神经中枢”。{控制器的主要特点是采用内存程序控制方式，即在使用计算机时，必须预先编写（或由编译程序自动生成）由计算机指令组成的的程序并存入内存储器，由控制器依次读取并执行}控制器由程序计数器（PC）、指令寄存器（IR）、指令译码器（ID）、时序控制电路以及微操作控制电路等组成。软件系统包括系统软件、应用软件和工具软件三大类。由于软件的内容非常多，在此只作简单的说明。系统软件是为了对计算机的软硬件资源进行管理、提高计算机系统的使用效率和方便用户的各种通用软件，一般由计算机生产商提供。常用的系统软件有操作系统、程序设计语言翻译系统和实用程序（如驱动程序、连接程序、诊断程序等）。应用软件是专门为某一应用目的而编制的软件系统，常用的应用软件有字处理软件、表处理软件、统计分析软件、数据库管理系统、计算机辅助软件、实时控制与处理软件以及其它应用于国名经济各行的应用程序。工具软件主要包括下载、文件传输协议（FTP）、图像、浏览、截图压缩、防病毒等常用软件。

形式语言与自动机课后习题答案

形式语言与自动机课后作业答案第二章 4．找出右线性文法，能构成长度为1至5个字符且以字母为首的字符串。答：G={N,T,P,S} 其中N={S,A,B,C,D} T={x,y} 其中x∈{所有字母} y∈{所有的字符} P如下: S→x S→xA A→y A→yB B→y B→yC C→y C→yD D→y 6．构造上下文无关文法能够产生 L={ω/ω∈{a,b}*且ω中a的个数是b的两倍} 答：G={N,T,P,S} 其中N={S} T={a,b} P如下: S→aab S→aba S→baa S→aabS S→aaSb S→aSab S→Saab S→abaS S→abSa S→aSba S→Saba S→baaS S→baSa S→bSaa S→Sbaa 7．找出由下列各组生成式产生的语言（起始符为S） (1)S→SaS S→b (2)S→aSb S→c (3)S→a S→aE E→aS 答：（1）b(ab)n /n≥0}或者L={(ba)n b/n≥0} (2) L={a n cb n /n≥0} (3)L={a2n+1 /n≥0} 第三章 1．下列集合是否为正则集，若是正则集写出其正则式。（1）含有偶数个a和奇数个b的{a,b}*上的字符串集合（2）含有相同个数a和b的字符串集合（3）不含子串aba的{a,b}*上的字符串集合答：（1）是正则集，自动机如下 (2) 不是正则集，用泵浦引理可以证明，具体见17题（2）。

(3) 是正则集先看L’为包含子串aba的{a,b}*上的字符串集合显然这是正则集，可以写出表达式和画出自动机。（略）则不包含子串aba的{a,b}*上的字符串集合L是L’的非。根据正则集的性质，L也是正则集。 4．对下列文法的生成式，找出其正则式（1）G=({S,A,B,C,D},{a,b,c,d},P,S),生成式P如下： S→aA S→B A→abS A→bB B→b B→cC C→D D→bB D→d （2）G=({S,A,B,C,D},{a,b,c,d},P,S),生成式P如下： S→aA S→B A→cC A→bB B→bB B→a C→D C→abB D→d 答：(1) 由生成式得： S=aA+B ① A=abS+bB ② B=b+cC ③ C=D ④ D=d+bB ⑤ ③④⑤式化简消去CD，得到B=b+c(d+bB) 即B=cbB+cd+b =>B=(cb)*(cd+b) ⑥ 将②⑥代入① S=aabS+ab(cb)*(cd+b)+(cb)*(cd+b) =>S=(aab)*(ab+ε)(cb)*(cd+b) (2) 由生成式得： S=aA+B ① A=bB+cC ② B=a+bB ③ C=D+abB ④ D=dB ⑤ 由③得 B=b*a ⑥ 将⑤⑥代入④ C=d+abb*a=d+ab+a ⑦ 将⑥⑦代入② A=b+a+c(d+b+a) ⑧ 将⑥⑧代入① S=a(b+a+c(d+ab+a))+b*a =ab+a+acd+acab+a+b*a 5.为下列正则集，构造右线性文法： (1){a,b}* (2)以abb结尾的由a和b组成的所有字符串的集合

计算机科学技术导论论文

专业导论（论文）谈谈你对计算机专业的认识及四年学习的设想学院计算机学院专业软件工程年级2007级姓名李云松学号3107006836 教师傅秀芬 2007年12月12日广东工业大学计算机学院制

专业导论论文计算机的发明是20世纪最卓越的成就之一。计算计的广泛应用极大的促进了生产力的发展，它在当今信息化的社会中已经成为必不可少的工具。什么是计算机实际上，计算机是一种能够按照事先存储的程序，自动、高速地对数据进行输入、处理、输出和储存的系统。一个计算机系统包括硬件和软件两大部分。硬件是由电子的、磁性的、机械的器件组成的物理实体，包括运算器、存储器、控制器、输入设备与输出设备等5个基本组成部分。软件则是程序和有关文档的总称，包括系统软件、应用软件和工具软件三类。计算机硬件系统下面简单介绍一下硬件系统的5个部分。硬件系统的五个部分中控制器是指挥计算机的各个部件按照指令的功能要求协调工作的部件，是计算机的“神经中枢”。{控制器的主要特点是采用内存程序控制方式，即在使用计算机时，必须预先编写（或由编译程序自动生成）由计算机指令组成的的程序并存入内存储器，由控制器依次读取并执行}控制器由程序计数器（PC）、指令寄存器（IR）、指令译码器（ID）、时序控制电路以及微操作控制电路等组成。运算器是对二进制数进行运算的部件。它在控制器的控制下执行程序中的指令，完成各种算术运算、逻辑运算、比较运算、移位运算以及字符运算。运算器由算术、逻辑部件（ALU）、寄存器等组成。存储器是用来存储数据和程序的部件。由于计算机的信息都是以二进制形式表示的，所以必须使用具有两种稳定状态的物理器件来存储信息。根据功能不同，存储器一般可分为内存储器和外存储器两种类型。内存储器（又称为主存储器，又称为内存或主存）用来存放现行程序的指令和数据，具有存取速度快、可直接与运算器及控制器交换信息等特点，但其容量一般不大。外存储器（又称为辅助存储器，简称为外存或辅存）用来存放需要长期保存的信息。其特点是存储容量大、成本低。不能直接和运算器、控制器交换信息，需要时可成批的和内存储器交换信息。外存储器主要有软磁盘、硬磁盘以及光盘等。

形式语言与自动机理论试题答案解析

形式语言与自动机理论试题答案解析一、按要求完成下列填空 1. 给出集合{Φ,{Φ}}和集合{ε,0,00}的幂集（2x4'） (1) {Φ,{Φ},{{Φ}},{Φ,{Φ}}} (2) {Φ,{ε},{0},{00},{ε,0},{ε,00},{0,00},{ε,0,00}} 2. 设∑={0,1},请给出∑上的下列语言的文法（2x5'） (1)所有包含子串01011的串 S →X01011Y X →ε|0X|1X Y →ε|0Y|1Y (2)所有既没有一对连续的0，也没有一对连续的1的串 A →ε |A ’|A ” A’ →0|01|01A ’ A ” →1|10|10A ” 3. 构造识别下列语言的DFA 2x6' (1) {x|x ∈{0，1}+且x 以0开头以1结尾} （设置陷阱状态，当第一个字符为1时，进入陷阱状态） 1 S 1 1 0,10 (2) {x|x ∈{0，1} + 且x 的第十个字符为1} （设置一个陷阱状态，一旦发现x 的第十个字符为0，进入陷阱状态） 1S 0,1 0,10,10,10,110,0,10,10,10,1 0,1

二、判断（正确的写T ，错误的写F ） 5x2' 1.设1R 和2R 是集合{a,b,c,d,e}上的二元关系，则 3231321)(R R R R R R R ? ( T ) 任取(x.,y),其中x,y },,,,{e d c b a ∈，使得321)(),(R R R y x ∈。 )),(),((321R y z R R z x z ∈∧∈?? },,,,{e d c b a z ∈ )),(),(),((321R y z R z x R z x z ∈∧∈∧∈?? )),(),(()),(),((3231R y z R z x z R y z R z x z ∈∧∈?∧∈∧∈?? 3231),(),(R R y x R R y x ∈∧∈? 3231),(R R R R y x ∈? 2.对于任一非空集合A ，Φ?A 2 ( T ) 3.文法G ：S A|AS A a|b|c|d|e|f|g 是RG ( F ) 4.3型语言 2型语言 1型语言 0型语言 ( F ) 5.s （rs+s ）*r=rr *s （rr *s ）* ( F ) 不成立，假设r,s 分别是表示语言R ，S 的正则表达式，例如当R={0}，S={1}, L(s(rs+s)*r)是以1开头的字符串，而L(rr*s(rr*s)*)是以0开头的字符串.L(s(rs+s)*r) ≠ L(rr*s(rr*s)*) 所以s(rs+s)*r ≠ rr*s(rr*s)*,结论不成立三、设文法G 的产生式集如下，试给出句子aaabbbccc 的至少两个不同的推导（12分）。 aSBC aBC S |→ ab aB → bB →bb CB →BC bC →bc cC →cc

编译原理论文

《编译原理》课程论文编译程序是现代计算机系统的基本组成部分之一，而且多数计算机系统都配有不止一个高级语言的编译程序，对有些高级语言甚至配置了几个不同性能的编译程序。从功能上讲，一个编译程序就是一个语言翻译程序。语言翻译程序把一种源语言书写的程序翻译成另一种目标语言的等价程序，所以总的说编译程序是一种翻译程序，其源程序是高级语言，目标语言程序是低级语言。编译程序完成从源程序到目标程序的翻译工作，是一个复杂的整体的过程。从概念上来讲，一个编译程序的整个工作过程是划分成几个阶段进行的，每个阶段将源程序的一种表示形式转换成另一种表示形式，各个阶段进行的操作在逻辑上是紧密连接在一起的。一般一个编译过程是词法分析、语法分析、语义分析、中间代码生成、代码优化和目标代码生成。编写编译器的原理和技术具有十分普遍的意义，以至于在每个计算机工作者的职业生涯中，本书中的原理和技术都会反复用到。在这本书中，向我们介绍了文法的概念，在讲词法分析的章节中讲述了构造一个有穷自动机的方法，以及如何将一个不确定的有穷自动机转化成确定的有穷自动机和有穷自动机的最小化等方法。词法分析相对来说比较简单。可能是词法分析程序本身实现起来很简单吧，很多没有学过编译原理的人也同样可以写出各种各样的词法分析程序。不过编译原理在讲解词法分析的时候，重点把正则表达式和自动机原理加了进来，然后以一种十分标准的方式来讲解词法分析程序的产生。这样的做法道理很明显，就是要让词法分析从程序上升到理论的地步。词法分析中的重点是有穷自动机DFA的生成以及DFA和正规式与正规文法的关系。还要熟练掌握NFA转换为DFA的方法及DFA的化简。词法分析的核心应该是构建DFA，最后维护一个状态转移表。通过转态转移的结果来识别词性。DFA的思想和字典树很像。NFA通过求每个状态的闭包后构造出的自动机与DFA等价。正则表达式闭包，连接，或三种操作都有相应的NFA与其等价。所以正则表达式==NFA==DFA。DFA状态最小化算法化简DFA。LL(1)文法主要就是根据FIRST集判断向哪条路径走，来避免回溯；LR(0)文法构造项

我的专业导论论文

专业导论（论文）学院计算机学院专业班级姓名学号 2012年11月27日广东工业大学计算机学院制

我对所学专业的认识及我大学四年的规划与设想对计算机及计算机科学体系的理解计算机现代社会快速发展，计算机已经走进千家万户，越来越普及。并且它在日常生活以及工业方面发挥的作用越来越大。在诞生初期，计算机主要是用来科学计算。如今，它快速发展，可以对数字、文字、图形、图像及声音等进行处理。计算机是一种能够按事先存储的程序，自动、高速地对数据进行输入、处理、输出和存储的系统。计算机由运算器、存储器、控制器、输入和输出设备五大部分组成。以上为硬件部分，还有软件，软件则由系统软件、应用软件和工具软件三大部分组成。计算机的发展非常迅速。最初的计算机是电子管计算机，然后由电子管计算机发展成晶体管计算机，进而发展成大规模和超大规模的集成电路计算机。计算机具有如下特点：1.运算速度快2.运算精度高3.具有记忆力4.具有逻辑判断力5.存储程序。计算机的用途：1.科学计算2.数据处理3.实时监控4.人工智能5.计算机辅助工程和辅助教育6.娱乐和游戏等。计算机学科体系计算机学科体系包含了计算机理论、硬件、软件、网络及应用等领域。计算机理论的研究内容：1.离散数学 2.算法分析理论 3.形式语言及自动机理论4.程序设计理论语言5.程序设计方法学。计算机硬件的研究内容：1.元器件与存储介质 2.微电子技术 3.计算机组成原理 4.微型计算机技术 5.计算机体系结构。计算机软件的研究内容：1.程序设计语言的设计 2.数据结构与算法 3.程序

设计语言翻译系统 4.操作系统 5.数据库系统 6.算法设计与分析7.软件工程学8.可视化技术。计算机网络的研究内容：1.网络结构2.数据通信与网络协议3.网络服务 4.网络安全。计算机应用的研究内容：1.软件开发工具 2.完善既有的应用系统3.开拓新的应用领域4.人——机工程。计算机科学体系中包含了大量的内容，各部分内容看似互不关联，实际上却是联系在一起的。由于它的领域太广泛，所以我们要学懂各个部分，然后专门深入研究某一领域的应用。只有这样，我们才能有自己的专长，并且对其他方面也有了解,日后才能更好地找到工作。计算机系统硬件计算机由五大部分组成。其中控制器和运算器是核心部分，成为中央处理器，简称CPU。对于微型机，其系统由系统单元、输入输出系统、输入设备、输出设备和辅助存储设备组成。微型计算机的系统单元包括：系统主办与时钟频率、电子数据与指令、微处理器、主存储器。系统主板又称底板或母板，它是整个计算机系统的通信网，系统单元的每个元器件直接连接到系统主板，它们通过系统主板进行数据的交换。系统时钟用于控制计算机操作的速度，这个速度用兆赫（MHz）表示。微处理器接收来自各种输入设备的数据，并处理、输出这些数据。微处理器具有两个基本部件：控制单元和算术/逻辑单元。主存储器又称为内存储器或内存，是指能够通过指令中的地址直接访问的存储器，它被用来存储正在被CPU使用的程序和数据。

西安交通大学计算机硕士培养方案

西安交通大学《计算机科学与技术》学科攻读硕士学位研究生培养方案一、培养目标 1．培养德、智、体全面发展，具有强烈的社会责任感、能为社会主义市场经济和现代化建设服务的高级科学技术专门人才。 2．在计算机科学与技术领域具有坚实的理论基础和系统的专门知识，具有较强的综合分析和独立解决实际问题的能力以及从事科学技术研究、教学及开发应用的能力。 3．具有求实严谨的科学态度，为科学事业勇于创新的精神以及团结协作的团队作风。二、学科设置计算机科学与技术为一级学科，下设三个二级学科：“计算机系统结构”、“计算机软件与理论”、“计算机应用技术”。硕士研究生按一级学科培养。三、研究方向本专业目前有下列研究方向： 1.高性能计算机系统 2.计算机网络 3.分布式系统与中间件技术 4.数据库系统 5.信息与网络安全技术 6.人工智能与智能计算机系统 7.程序设计语言的理论与实现 8.面向对象的软件开发方法和技术 9.数据挖掘与知识发现 10. 基于Internet的信息处理系统 11. 多媒体技术与科学计算可视化 12. 人机交互技术 13. 计算机模拟仿真四、培养方式 1．为了保证硕士生新生入学时教学计划及时执行，在研究生录取工作结束后、研究生进校之前，由导师先制订硕士生第一学期的选课计划。原则上第一学期（秋上）的课程均为学位课；硕士生进校后1 周内由导师与硕士生共同商定制订全面培养计划。 2. 对硕士生的培养采取课程学习和论文工作并重的方式，论文工作时间不得少于一年。 3. 整个培养过程应贯彻理论联系实际的方针，使硕士生掌握本专业的

清华大学计算机科学与技术专业课程表

信息学院本科指导性教学计划(公共课) 第一学年秋季学期课号课程名学分周学时考试或考查说明及主要先修课 1061002 2 思想道德修养 2 2 考查 1064043 3 英语选修 2 2 考查 1042087 4 一元微积分 4 4 考试 1042068 4 几何与代数（1） 4 4 考试 20240013 离散数学（1） 3 3 考试 20230093 计算机语言与程序计 3 3 考试 30250023 计算机语言与程序计 3 3 考试 30240233 程序设计基础 3 3 考试四选一 3410006 3 程序设计基础 3 3 考试 30210041 信息科学技术概论 1 1 考查春季学期 00501622 毛泽东思想概论 3 2 考试 1064044 3 英语选修 2 2 考查 1042088 4 多元微积分 4 4 考试一元微积分 1042069 2 几何与代数(2) 2 2 考试几何与代数(1) 二选一 1042091 3 几何与代数(2) 3 3 考试几何与代数(1) 1043048 4 大学物理B(1) 4 4 考试一元微积分 1043034 4 大学物理 (1)(英) 4 4 考试一元微积分三选一 1043052 5 大学物理A(1) 5 5 考试一元微积分 2022021 4 电路原理 4 4 考试 2022022 1 电路原理实验 1 1 考查

第二学年秋季学期课号课程名学分周学考试或考查说明及主要先修课 10420753 高等微积分 2 2 考试一元微积分 10420252 复变函数引论 2 2 考试一元微积分二选一复变函数 3 3 考试一元微积分 10430535 大学物理A(2) 5 5 考试大学物理A(2) 20250093 电子技术基础 3 3 考试电路原理二选一 30230563 数字逻辑电路 3 3 考试电路原理电子技术基础实验 2 2 考查跨学期课，本学期完成1学分10420262 数理方程引论 2 2 考查不修该课程 20130342 工程图学基础 2 2 考试春季学期 10420243 随机数学方法 3 3 考试二选一 10420803 概率论与数理统计 3 3 考试数字逻辑电路 3 3 考试电路原理电子技术基础电子技术系列实验 2 2 考查跨学期课，本学期完成1学分30230104 信号与系统 4 4 考试微积分电路复二选一40250144 信号与系统分析 4 4 考试变几何与代数 40240013 系统分析与控制 3 3 考试微积分电路复二选一40250074 自动控制理论(1) 4 4 考试变几何与代数 3025 数据结构 3 3 考试四选一34100044 数据结构与算法 4 4 考试微电子学导论 3 3 考试半导体器件与集成电路 3 3 考试三选一集成电路原理与设计 3 3 考试物理、生物类课程≥ 2 2 20240023 离散数学（2）（选）3 3 考试夏季学期电子技术课程设计 3 3 考查电子技术基础 Java语言（选） 2 2 考查计算机语言与程序设计二选一语言（选） 2 2 考查计算机语言与程序设计

编译原理论文

编译原理心得编译原理是计算机及相关专业的一门重要专业课程，在计算机科学中有很重要的地位和作用，已被国内外高校列为计算机专业的主要课程。它主要介绍了高级程序设计语言编译程序构造的一般原理、基本设计方法、主要实现技术和一些自动构造工具。通过该课程的学习，对提高学生计算机软件素质，使学生真正认识计算机信息处理实质并综合运用所学的软件设计技术来分析问题等具有很大作用。该课程理论性与实践性都很强，我们在学习是普遍感到内容非常抽象，不易理解，内容多且繁琐，难以完整、全面地掌握编译原理的有关知识，更不用说灵活运用编译原理知识从事相关设计或应用于其他领域。虽然只有少数人从事编译方面的工作，但是这门课在理论、技术、方法上都对我们提供了系统而有效的训练，有利于提高软件人员的素质和能力。采用有用的资助手段增强课堂教学效果。基于Internet网络和多媒体技能，资助手段有种种千般的情势，可以借用有：讨论学习模式、探索学习模式、提供种种资源库的网上资助教学应用模式。在Internet上实现讨论学习的要领有多种，最简略实用的是使用现有的电子通告牌体系（BBS）,这种体系具有用户管理、讨论管理、文章讨论、实时讨论，用户留言、电子信件等诸多功效。编译原理在学习历程，门生题目难点不能逐一与老师举行面临面举行，那末议决网络，可以题目果然，老师创建相应的主题，门生可以在自己学习的特定地域发言，门生之间可以举行交换，全部的题目都果然化。探索学习模式。这种模式一样平常都是由某些教诲机构设立一些适当特定门生工具的题目，议决Internet向门生公布，要求门生解答；同时提供大量的、与题目相干的信息资源供门生在解决题目历程中查阅。这种模式彻底转变了传统教学历程中门生被动继承的状态，而使门生处于积极自动的职位地方，因而能有用地引发门生的学习兴趣和创造性。在我们学习编译原理以前，都认为编译原理只能应用在写程序语言的编译器上,觉得用处不大,学习兴趣不高。而在后来的学习中，我们逐渐认识到计算机专业的学生，除了要会编写程序语言之外，还应该了解它是如何被计算机所识别，这才是真正并且透彻地学习软件。另外，编译器中每一个模块的编写，都能对我们的编程能力的提高有很大帮助。在今后若从事软件工程，这门课程也能够对编写程序有所帮助。为了能够系统掌握这门专业课，我们把编译原理分为以下几个模块：（1）语言和文法；（2）词法分析；（3）语法分析；（4）语义分析和中间代码生成；（5）代码优化和目标代码生成；（6）关于实践。在学习的开始，我们需要掌握什么是编译，编译分为哪些阶段，编译程序和解释程序的区别等等。在做好了这些方面的准备后，开始了系统的学习。语言和文法语言和文法部分的知识包括文法基本概念及文法的二义性。基本概念有文法定义、推导、句型、句子等等。二义性文法是通过画语法树的方法来证明。词法分析词法分析相对来说比较简单。可能是词法分析程序本身实现起来很简单吧，很多没有学过编

软件工程一级学科专业

软件工程（一级学科）专业博士生培养方案一、培养目标培养适应建设有中国特色社会主义需要的、热爱祖国、遵纪守法、德智体全面发展、具备严谨科学态度和敬业精神的软件工程专业人才。通过博士阶段的学习，具有软件工程学科内全面而扎实的基础理论知识，有一定的独立见解，教学、科学及组织能力较强，掌握某一方向的最新技术，能较好地从事该方向的教学、科研与开发工作。学位论文应具有一定的创造性或较大的应用价值。二、研究方向本学科博士生的培养主要包括软件工程理论与方法、软件工程技术、软件服务工程、领域软件工程等专业领域。研究方向包括：（1）复杂软件理论与自动化（2）软件分析与测试技术（3）分布式软件与领域工程（4）形式化方法与技术（5）领域软件工程与信息系统（6）网构软件与服务工程（7）软件自适应（8）软件测试技术与过程管理（9）社会网络技术（10）软件数据挖掘等。三、招生对象通过学校组织的博士生人数考试招收合格的博士生源有： 1．应届硕士毕业生 2．提前攻博硕士生 3．往届硕士或同等学历四、学习年限 1．一般情况下，学习年限为四年 2．特别优秀者可适当提前 3．来不及完成博士论文者可适当延长五、课程设置现代科学技术革命与马克思主义第一外语第二外语软件工程方法与技术进展软件自动化软件工程改进软件可靠性方法先进操作系统经验软件工程方法软件形式化方法软件需求工程机器学习与数据挖掘多媒体技术进展六、培养方式博士生招生录取时明确导师，由导师负责成立指导小组，制定培养计划。由博士生导师和培养小组负责全部培养工作。公共课以讲授为主，辅以自学。根据研究方向和科研工作的需要，选读若干门专业选修课。专业课以讲授、自学、讨论相结合的形式，要求博士生阅读有关的专业文献，参加讨论班、学术报告等各种学术活动。

形式语言与自动机理论蒋宗礼第一章参考答案

第一章参考答案 1.1请用列举法给出下列集合。（吴贤珺02282047） ⑴你知道的各种颜色。解：{红，橙，黄，绿，青，蓝，紫} ⑵大学教师中的各种职称。解：{助教，讲师，副教授，教授} ⑶你所学过的课程。解：{语文，数学，英语，物理，化学，生物，历史，地理，政治} ⑷你的家庭成员。解：{父亲，母亲，妹妹，我} ⑸你知道的所有交通工具。解：{汽车，火车，飞机，轮船，马车} ⑹字母表{a , b}上长度小于4的串的集合。解：{a,b,aa,bb,ab,ba,aaa,aab,aba,abb,baa,bab,bba,bbb} ⑺集合{1,2,3,4}的幂集。解：{Φ,{1},{2},{3},{4},{1,2},{1,3},{1,4},{2,3},{2,4},{3,4},{1,2,3},{1,2,4}, {1,3,4},{2,3,4},{1,2,3,4} } ⑻所有的非负奇数。解：{1,3,5,7,…} ⑼0～100的所有正整数。解：{1,2,3, (100) (10) 1～10之间的和为10的整数集合的集合。解：设所求的集合为A，集合A中的元素为A i（i=1,2,3,…），A i也是集合，A i中的元素在1～10之间，并且和为10。根据集合元素的彼此可区分性，可以计算出A i中元素的最多个数，方法是：把1开始的正整数逐个相加，直到等于10（即10=1+2+3+4），这样， A i中最多有4个元素。原因是：从最小的1开始，每次加入新的元素都只依次增加1，这样相加的和最小，要加到10，元素个数就最多。求出最大的∣A i∣＝4后，再求出元素个数为3，2，1的集合就可以了。故A={{10},{1,9},{2,8},{3,7},{4,6},{1,2,7},{1,3,6},{1,4,5},{2,3,5},{1,2,3,4}} 1.2 请用命题法给出下列集合

电梯建模

电梯建模姓名：*** 学号：******** 班级：***** 引文：自然语言描述对电梯系统的要求：在一幢m层的大厦中需要一套控制n部电梯的产品，要求这n部电梯按约束条件c1，c2和c3在楼层间移动。对此要求进行建模。一、电梯按钮 C1：每部电梯内有m个按钮，每个按钮代表一个楼层。当按下一个按钮时该按钮指示灯亮，同时电梯驶向相应的楼层，到达相应的楼层时指示灯熄灭。 C2：除了大厦的最底层与最高层之外，每层楼都有两个按钮分别请求电梯上行和下行。这两个按钮之一被按下是相应的指示灯亮，当电梯到达此楼层时灯熄灭，电梯向要求的方向移动。 C3：当对电梯没有请求时，它关门并停在相应的楼层。现在使用一个扩展的有穷状态机对本产品进行规格说明。这个问题中有两个按钮集。N部电梯中的每一部都有m个按钮，一个按钮对应一个楼层。因为这m*n个按钮都在电梯中，所以称他们为电梯按钮。此外，每层楼有两个按钮，一个请求向上，另一个请求向下，这些按钮称为楼层按钮。电梯按钮的状态转换图令EB(e,f)表示按下电梯e内的按钮并请求到f层去。EB(e,f)有两个状态： EBON(e,f)：电梯按钮（e,f）打开 EBOFF(e,f)：电梯按钮（e,f）关闭如果电梯按钮（e,f）发光且到f层，该按钮将熄灭。相反如果按钮熄灭，则按下它时，按钮将发光。上述两个描述中包含了两个事件，它们分别是： EBP(e,f)：电梯按钮（e,f）被按下 EBP(e,f)：电梯e到达f层为了定义这些事件和状态相联系的状态转换规则，需要一个谓词V(e,f)，它的含义如下： V(e,f)：电梯e停在f层如果电梯按钮（e,f）处于关闭状态【当前状态】，而且电梯按钮（e,f）被按下【事件】，而且电梯e不再f层【谓词】，则该电梯按钮打开发光【下个状态】。状态转换的形式化描述如下：EBOFF(e,f)+EBP(e,f)+notV(e,f)=>EBON(e,f) 反之，如果电梯到达f层，而且电梯按钮是打开的，于是它就会熄灭。这条转换规则可以形式化描述为： EBON (e,f)+EAF(e,f) =>EBOFF(e,f) 二、楼层按钮令FB（d,f）表示f层电梯向d方向的按钮，如图：