PAGE1.以下哪個正則表達(dá)式可以匹配所有以“ab”開頭且以“ba”結(jié)尾的字符串？

-A.`ab.*ba`

-B.`ab+ba`

-C.`abba`

-D.`ab|ba`

**參考答案**:A

**解析**:`ab.*ba`表示以“ab”開頭，中間可以有任意字符（包括空字符），并以“ba”結(jié)尾的字符串。

2.給定文法`S→aSb|ε`，該文法生成的語言是什么？

-A.所有由相同數(shù)量的a和b組成的字符串

-B.所有由a和b組成的字符串

-C.所有由a和b組成的回文字符串

-D.所有由a和b組成的字符串，且a和b的數(shù)量相等

**參考答案**:D

**解析**:該文法生成的語言是所有由相同數(shù)量的a和b組成的字符串，如“ab”、“aabb”等。

3.以下哪個自動機(jī)可以識別語言`{a^nb^n|n≥0}`？

-A.有限自動機(jī)

-B.下推自動機(jī)

-C.圖靈機(jī)

-D.線性有界自動機(jī)

**參考答案**:B

**解析**:該語言需要計(jì)數(shù)a和b的數(shù)量，有限自動機(jī)無法實(shí)現(xiàn)，而下推自動機(jī)可以通過棧來實(shí)現(xiàn)計(jì)數(shù)。

4.給定正則表達(dá)式`(a|b)*`，以下哪個字符串不能被該表達(dá)式匹配？

-A.“abab”

-B.“aabb”

-C.“”

-D.“baaab”

**參考答案**:C

**解析**:`(a|b)*`可以匹配任意由a和b組成的字符串，包括空字符串“”。

5.以下哪個語言是上下文無關(guān)語言？

-A.`{a^nb^nc^n|n≥0}`

-B.`{a^nb^n|n≥0}`

-C.`{a^nb^mc^n|n,m≥0}`

-D.`{a^nb^mc^m|n,m≥0}`

**參考答案**:B

**解析**:`{a^nb^n|n≥0}`是上下文無關(guān)語言，因?yàn)樗梢杂缮舷挛臒o關(guān)文法生成。

6.給定文法`S→aS|bS|ε`，該文法生成的語言是什么？

-A.所有由a和b組成的字符串

-B.所有由a和b組成的回文字符串

-C.所有由a和b組成的字符串，且a和b的數(shù)量相等

-D.所有由a和b組成的字符串，且a和b的數(shù)量不等

**參考答案**:A

**解析**:該文法生成的語言是所有由a和b組成的字符串，包括空字符串。

7.以下哪個自動機(jī)可以識別語言`{a^nb^m|n,m≥0}`？

-A.有限自動機(jī)

-B.下推自動機(jī)

-C.圖靈機(jī)

-D.線性有界自動機(jī)

**參考答案**:A

**解析**:該語言不需要計(jì)數(shù)，有限自動機(jī)可以識別。

8.給定正則表達(dá)式`a*b*`，以下哪個字符串不能被該表達(dá)式匹配？

-A.“aab”

-B.“abb”

-C.“aabb”

-D.“ba”

**參考答案**:D

**解析**:`a*b*`表示任意數(shù)量的a后跟任意數(shù)量的b，因此“ba”不能被匹配。

9.以下哪個語言是正則語言？

-A.`{a^nb^n|n≥0}`

-B.`{a^nb^m|n,m≥0}`

-C.`{a^nb^nc^n|n≥0}`

-D.`{a^nb^mc^m|n,m≥0}`

**參考答案**:B

**解析**:`{a^nb^m|n,m≥0}`是正則語言，因?yàn)樗梢杂烧齽t表達(dá)式`a*b*`表示。

10.給定文法`S→aSb|bSa|ε`，該文法生成的語言是什么？

-A.所有由a和b組成的字符串

-B.所有由a和b組成的回文字符串

-C.所有由a和b組成的字符串，且a和b的數(shù)量相等

-D.所有由a和b組成的字符串，且a和b的數(shù)量不等

**參考答案**:C

**解析**:該文法生成的語言是所有由a和b組成的字符串，且a和b的數(shù)量相等。

11.以下哪個自動機(jī)可以識別語言`{a^nb^nc^n|n≥0}`？

-A.有限自動機(jī)

-B.下推自動機(jī)

-C.圖靈機(jī)

-D.線性有界自動機(jī)

**參考答案**:C

**解析**:該語言需要計(jì)數(shù)a、b和c的數(shù)量，圖靈機(jī)可以實(shí)現(xiàn)這種復(fù)雜的計(jì)數(shù)。

12.給定正則表達(dá)式`(a|b)*c`，以下哪個字符串不能被該表達(dá)式匹配？

-A.“abc”

-B.“c”

-C.“aabbc”

-D.“bac”

**參考答案**:B

**解析**:`(a|b)*c`表示任意數(shù)量的a和b后跟一個c，因此“c”不能被匹配。

13.以下哪個語言是上下文無關(guān)語言？

-A.`{a^nb^nc^n|n≥0}`

-B.`{a^nb^mc^m|n,m≥0}`

-C.`{a^nb^mc^n|n,m≥0}`

-D.`{a^nb^mc^p|n,m,p≥0}`

**參考答案**:B

**解析**:`{a^nb^mc^m|n,m≥0}`是上下文無關(guān)語言，因?yàn)樗梢杂缮舷挛臒o關(guān)文法生成。

14.給定文法`S→aS|bS|cS|ε`，該文法生成的語言是什么？

-A.所有由a、b和c組成的字符串

-B.所有由a、b和c組成的回文字符串

-C.所有由a、b和c組成的字符串，且a、b和c的數(shù)量相等

-D.所有由a、b和c組成的字符串，且a、b和c的數(shù)量不等

**參考答案**:A

**解析**:該文法生成的語言是所有由a、b和c組成的字符串，包括空字符串。

15.以下哪個自動機(jī)可以識別語言`{a^nb^mc^p|n,m,p≥0}`？

-A.有限自動機(jī)

-B.下推自動機(jī)

-C.圖靈機(jī)

-D.線性有界自動機(jī)

**參考答案**:A

**解析**:該語言不需要計(jì)數(shù)，有限自動機(jī)可以識別。

16.給定正則表達(dá)式`a+b+c+`，以下哪個字符串不能被該表達(dá)式匹配？

-A.“aabbcc”

-B.“abc”

-C.“aabcc”

-D.“abcc”

**參考答案**:D

**解析**:`a+b+c+`表示至少一個a后跟至少一個b后跟至少一個c，因此“abcc”不能被匹配。

17.以下哪個語言是正則語言？

-A.`{a^nb^n|n≥0}`

-B.`{a^nb^m|n,m≥0}`

-C.`{a^nb^nc^n|n≥0}`

-D.`{a^nb^mc^m|n,m≥0}`

**參考答案**:B

**解析**:`{a^nb^m|n,m≥0}`是正則語言，因?yàn)樗梢杂烧齽t表達(dá)式`a*b*`表示。

18.給定文法`S→aSb|bSa|aSa|bSb|ε`，該文法生成的語言是什么？

-A.所有由a和b組成的字符串

-B.所有由a和b組成的回文字符串

-C.所有由a和b組成的字符串，且a和b的數(shù)量相等

-D.所有由a和b組成的字符串，且a和b的數(shù)量不等

**參考答案**:B

**解析**:該文法生成的語言是所有由a和b組成的回文字符串。

19.以下哪個自動機(jī)可以識別語言`{a^nb^mc^p|n=m+p}`？

-A.有限自動機(jī)

-B.下推自動機(jī)

-C.圖靈機(jī)

-D.線性有界自動機(jī)

**參考答案**:C

**解析**:該語言需要復(fù)雜的計(jì)數(shù)和比較，圖靈機(jī)可以實(shí)現(xiàn)這種復(fù)雜的計(jì)算。

20.給定正則表達(dá)式`(a|b)*c(a|b)*`，以下哪個字符串不能被該表達(dá)式匹配？

-A.“abc”

-B.“c”

-C.“aabbc”

-D.“bac”

**參考答案**:B

**解析**:`(a|b)*c(a|b)*`表示任意數(shù)量的a和b后跟一個c，再跟任意數(shù)量的a和b，因此“c”不能被匹配。

21.以下哪個正則表達(dá)式可以匹配所有以“ab”開頭的字符串？

-A.`ab*`

-B.`ab+`

-C.`ab?`

-D.`ab.`

**參考答案**:B

**解析**:`ab+`表示匹配以“ab”開頭，并且“b”可以重復(fù)一次或多次的字符串。

22.給定文法\(S\rightarrowaS|b\)，以下哪個字符串可以被該文法生成？

-A.`aab`

-B.`baa`

-C.`aba`

-D.`bbb`

**參考答案**:A

**解析**:該文法生成的所有字符串都以“a”開頭，并以“b”結(jié)尾，因此只有“aab”符合。

23.以下哪種自動機(jī)可以識別正則語言？

-A.圖靈機(jī)

-B.下推自動機(jī)

-C.有限自動機(jī)

-D.線性有界自動機(jī)

**參考答案**:C

**解析**:有限自動機(jī)（FA）是識別正則語言的最基本模型。

24.給定正則表達(dá)式\((a|b)*\)，以下哪個字符串不能被匹配？

-A.`abab`

-B.`baab`

-C.`aabb`

-D.`aaab`

**參考答案**:無

**解析**:該正則表達(dá)式可以匹配所有由“a”和“b”組成的字符串，因此所有選項(xiàng)都可以被匹配。

25.以下哪個語句描述了下推自動機(jī)（PDA）的特點(diǎn)？

-A.PDA只能識別正則語言

-B.PDA使用棧作為輔助存儲

-C.PDA不能處理上下文無關(guān)語言

-D.PDA的轉(zhuǎn)移函數(shù)不依賴于輸入符號

**參考答案**:B

**解析**:下推自動機(jī)（PDA）使用棧作為輔助存儲，可以識別上下文無關(guān)語言。

26.給定文法\(S\rightarrowaSb|\epsilon\)，以下哪個字符串不能被該文法生成？

-A.`ab`

-B.`aabb`

-C.`aaabbb`

-D.`ba`

**參考答案**:D

**解析**:該文法生成的所有字符串都是“a”和“b”的平衡串，因此“ba”不符合。

27.以下哪個正則表達(dá)式可以匹配所有以“a”開頭并以“b”結(jié)尾的字符串？

-A.`a*b*`

-B.`a.*b`

-C.`a+b+`

-D.`a?b?`

**參考答案**:B

**解析**:`a.*b`表示以“a”開頭，以“b”結(jié)尾，中間可以是任意字符的字符串。

28.以下哪種自動機(jī)可以識別上下文無關(guān)語言？

-A.有限自動機(jī)

-B.下推自動機(jī)

-C.圖靈機(jī)

-D.線性有界自動機(jī)

**參考答案**:B

**解析**:下推自動機(jī)（PDA）是識別上下文無關(guān)語言的基本模型。

29.給定正則表達(dá)式\(a(b|c)*d\)，以下哪個字符串不能被匹配？

-A.`abd`

-B.`acd`

-C.`abcd`

-D.`ad`

**參考答案**:D

**解析**:該正則表達(dá)式要求字符串以“a”開頭，以“d”結(jié)尾，中間可以是“b”或“c”的任意組合，因此“ad”不符合。

30.以下哪個語句描述了有限自動機(jī)（FA）的特點(diǎn)？

-A.FA可以使用棧作為輔助存儲

-B.FA的轉(zhuǎn)移函數(shù)依賴于輸入符號和棧頂符號

-C.FA的轉(zhuǎn)移函數(shù)只依賴于輸入符號和當(dāng)前狀態(tài)

-D.FA可以識別上下文無關(guān)語言

**參考答案**:C

**解析**:有限自動機(jī)（FA）的轉(zhuǎn)移函數(shù)只依賴于輸入符號和當(dāng)前狀態(tài)，不能使用棧。

31.給定文法\(S\rightarrowaS|bS|\epsilon\)，以下哪個字符串可以被該文法生成？

-A.`abab`

-B.`baab`

-C.`aabb`

-D.`aaab`

**參考答案**:A

**解析**:該文法生成的所有字符串都是由“a”和“b”組成的任意組合，因此“abab”符合。

32.以下哪個正則表達(dá)式可以匹配所有包含至少一個“a”和一個“b”的字符串？

-A.`a*b*`

-B.`a+b+`

-C.`(a|b)*`

-D.`a*b*|b*a*`

**參考答案**:D

**解析**:`a*b*|b*a*`表示字符串中至少包含一個“a”和一個“b”，且“a”和“b”的順序可以任意。

33.以下哪種自動機(jī)可以識別遞歸可枚舉語言？

-A.有限自動機(jī)

-B.下推自動機(jī)

-C.圖靈機(jī)

-D.線性有界自動機(jī)

**參考答案**:C

**解析**:圖靈機(jī)是識別遞歸可枚舉語言的基本模型。

34.給定正則表達(dá)式\((a|b)*a(a|b)*\)，以下哪個字符串不能被匹配？

-A.`aba`

-B.`baa`

-C.`aab`

-D.`bbb`

**參考答案**:D

**解析**:該正則表達(dá)式要求字符串中至少包含一個“a”，因此“bbb”不符合。

35.以下哪個語句描述了圖靈機(jī)的特點(diǎn)？

-A.圖靈機(jī)只能識別正則語言

-B.圖靈機(jī)使用棧作為輔助存儲

-C.圖靈機(jī)的轉(zhuǎn)移函數(shù)依賴于輸入符號和當(dāng)前狀態(tài)

-D.圖靈機(jī)可以識別遞歸可枚舉語言

**參考答案**:D

**解析**:圖靈機(jī)是識別遞歸可枚舉語言的基本模型，其轉(zhuǎn)移函數(shù)依賴于輸入符號、當(dāng)前狀態(tài)和磁帶上的符號。

36.給定文法\(S\rightarrowaSb|bSa|\epsilon\)，以下哪個字符串不能被該文法生成？

-A.`abab`

-B.`baab`

-C.`aabb`

-D.`aaab`

**參考答案**:D

**解析**: