题库试卷

【百年教育职业培训中心】形式语言与自动机理论-章节资料考试资料-哈尔滨工业大学 (2)

来源：百年教育职业培训中心　更新时间：2022-05-27 07:18:00

报名本机构合作学校，赠送复习资料，复习课程，确保录取。并且可以申请学校奖学金500元～1500元不等！答案：微信搜索【渝粤教育】公众号第1章测试基础知识1、【单选题】令字母表

报名本机构合作学校，赠送复习资料，复习课程，确保录取。并且可以申请学校奖学金500元～1500元不等！

第1章测试基础知识

1、【单选题】令字母表<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_aeb6a98a-56cb-40ef-8d0b-d83a27149066.png" style="white-space: normal;" />, 则克林闭包<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_fcd0b193-0039-4d6b-a000-dadff207d51e.png" style="white-space: normal;" />中元素的数量为？

A、有限个

B、可数无穷个

C、不可数无穷个

D、都有可能

2、【单选题】令字母表<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_aeb6a98a-56cb-40ef-8d0b-d83a27149066.png" style="white-space: normal;" />, 则克林闭包<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_fcd0b193-0039-4d6b-a000-dadff207d51e.png" style="white-space: normal;" />中元素的长度为？

A、只能是有限的

B、只能是无限的

C、可能是有限的，也可能是无限的

D、可能为0，或有限长，或无限长

3、【单选题】集合<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_38cb3ec7-195b-4fac-a26e-bfaa4f8127bf.png" style="white-space: normal;" /> 和 <img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_5cca86cc-0233-496e-bb7b-69fcacfe4297.png" style="white-space: normal;" />分别等于？

A、<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_13bd1406-575d-4913-b16e-68471121d382.png" style="white-space: normal;" />

B、<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_906b5844-cbd2-4e38-9c59-ef74fff86a20.png" style="white-space: normal;" />

C、<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_089c6f6a-8c45-42f0-a468-d5cde84c2bcb.png" style="white-space: normal;" />

D、<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_e2a10481-fc6c-4c68-9568-93b581e37b54.png" style="white-space: normal;" />

4、【单选题】集合<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_dd62fb2b-d0fb-4e22-93eb-7264d6999ce4.png" style="white-space: normal;" /> 和<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_da3d4a14-3453-47b3-bed7-9897915c6ee1.png" style="white-space: normal;" />分别等于？

A、<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_fd7bc9ea-27b0-445b-9a27-459b6ce3e3f9.png" style="white-space: normal;" />

B、<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_0a3624ef-c5df-4cfc-950d-572a56448c57.png" style="white-space: normal;" />

C、<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_b3339dee-db2e-4a05-9ff2-b7c016e73ead.png" style="white-space: normal;" />

D、<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_750300e9-208b-4fa7-89fe-8ead7711692d.png" style="white-space: normal;" />

5、【单选题】令字符串集合<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_051d7867-0b2a-4ba8-981e-42c311810087.png" style="white-space: normal;" />，则<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_38664643-8000-44ff-860e-7344b8505326.png" style="white-space: normal;" />和<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_5fded26f-36f1-4e8a-ac47-6c9369b72ef1.png" style="white-space: normal;" />分别等于？

A、<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_2b8312ca-84a2-4277-a31d-2ad5428dea6b.png" style="white-space: normal;" />

B、<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_f5346a9b-c037-499b-a338-6dbaea815ff2.png" style="white-space: normal;" />

C、<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_4ae31a52-2143-4f8d-8049-aafbec87f60e.png" style="white-space: normal;" />

D、<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_8019e1fa-812a-41b2-929b-603788eb0440.png" style="white-space: normal;" />

6、【单选题】令字符串集合<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_051d7867-0b2a-4ba8-981e-42c311810087.png" style="white-space: normal;" />，则<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_dda23f61-ee44-4ade-a9af-c859354b2853.png" style="white-space: normal;" />和<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_51fc61b5-9bea-4477-8b51-3f53ea4a5743.png" style="white-space: normal;" />分别等于？

A、<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_7bf9badd-f845-450d-813a-54b385c23c04.png" style="white-space: normal;" />

B、<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_73aab1dd-d453-44aa-9b0c-21045cadf4e0.png" style="white-space: normal;" />

C、<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_d9f4a1a1-db09-4d0f-a357-1297c720db85.png" style="white-space: normal;" />

D、<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_c47ce32e-c8bf-45d3-bb0d-1ab75fa24dbe.png" style="white-space: normal;" />

7、【判断题】字符串的长度可以是任意的，那么也可以是无穷长的。

A、正确

B、错误

8、【判断题】任意有穷集合的克林闭包一定是无穷集合。

A、正确

B、错误

9、【判断题】集合的克林闭包与正比包一定不相等

A、正确

B、错误

第2章测试有穷自动机

1、【单选题】由字符0和1构成且长度为偶数的全部字符串的DFA，至少需要几个状态？

A、2

B、1

C、3

D、0

2、【单选题】确定的有穷自动机中，“确定的”含义是：

A、状态转移是确定的

B、输入字符是确定的

C、状态是确定的

D、语言是确定的

3、【单选题】由字符0和1构成且含有偶数个1的DFA，至少需要几个状态？

A、2

B、3

C、1

D、4

4、【单选题】由字符0和1构成且含有奇数个1的DFA，至少需要几个状态？

A、2

B、1

C、3

D、4

5、【单选题】由字符0和1构成且含有奇数个1和偶数个0的DFA，至少需要几个状态？

A、1

B、2

C、3

D、4

6、【单选题】如果字母表<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_8af3797d-a441-4cbb-9e05-77bf0722e580.png" style="white-space: normal;" />, 以下哪个接受语言<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_946f4ef5-c45a-4e43-a3ec-2fa25b6f21e1.png" style="white-space: normal;" />的DFA？

A、<img src="http://edu-image.nosdn.127.net/615F175EBDE8CA01F829C2B941F20A05.png?imageView&thumbnail=890x0&quality=100" style="white-space: normal;" />

B、<img src="http://edu-image.nosdn.127.net/94399907807699206A7533085868B492.png?imageView&thumbnail=890x0&quality=100" style="white-space: normal;" />

C、<img src="http://edu-image.nosdn.127.net/6C27FB186A317D85C16FC06760654EBF.png?imageView&thumbnail=890x0&quality=100" style="white-space: normal;" />

D、<img src="http://edu-image.nosdn.127.net/CA005CD6E46457CA43F2B66919BBB3ED.png?imageView&thumbnail=890x0&quality=100" style="white-space: normal;" />

E、<img src="http://edu-image.nosdn.127.net/A47EAC3C6ED40E1DAED032890CF62C21.png?imageView&thumbnail=890x0&quality=100" style="white-space: normal;" />

7、【单选题】如果字母表<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_8af3797d-a441-4cbb-9e05-77bf0722e580.png" />, 以下哪个接受语言<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_ff7fc961-0585-4e64-b39f-2b10c935187e.png" />的DFA？

A、<img src="http://edu-image.nosdn.127.net/F3D46DF449653C02E14DAC4263F3505F.png?imageView&thumbnail=890x0&quality=100" style="white-space: normal;" />

B、<img src="http://edu-image.nosdn.127.net/3FC6066230463CA0EFF3CA647AB9E214.png?imageView&thumbnail=890x0&quality=100" style="white-space: normal;" />

C、<img src="http://edu-image.nosdn.127.net/76058F4E13F0CECC05C28EA17D5422F3.png?imageView&thumbnail=890x0&quality=100" style="white-space: normal;" />

D、<img src="http://edu-image.nosdn.127.net/1C19B34E0991F9FBBBAC5A27D1625F36.png?imageView&thumbnail=890x0&quality=100" style="white-space: normal;" />

E、<img src="http://edu-image.nosdn.127.net/AEB920CD459CF99BDF39C4A6A4809283.png?imageView&thumbnail=890x0&quality=100" style="white-space: normal;" />

8、【单选题】如果字母表<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_8af3797d-a441-4cbb-9e05-77bf0722e580.png" />, 以下哪个接受语言<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_3bf68c23-ae87-4bac-9222-560661ad201e.png" />的DFA？

A、<img src="http://edu-image.nosdn.127.net/F3D46DF449653C02E14DAC4263F3505F.png?imageView&thumbnail=890x0&quality=100" style="white-space: normal;" />

B、<img src="http://edu-image.nosdn.127.net/3FC6066230463CA0EFF3CA647AB9E214.png?imageView&thumbnail=890x0&quality=100" style="white-space: normal;" />

C、<img src="http://edu-image.nosdn.127.net/76058F4E13F0CECC05C28EA17D5422F3.png?imageView&thumbnail=890x0&quality=100" style="white-space: normal;" />

D、<img src="http://edu-image.nosdn.127.net/1C19B34E0991F9FBBBAC5A27D1625F36.png?imageView&thumbnail=890x0&quality=100" style="white-space: normal;" />

E、<img src="http://edu-image.nosdn.127.net/AEB920CD459CF99BDF39C4A6A4809283.png?imageView&thumbnail=890x0&quality=100" style="white-space: normal;" />

9、【单选题】如果字母表<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_8af3797d-a441-4cbb-9e05-77bf0722e580.png" style="white-space: normal;" />, 以下哪个接受语言<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_10095aa6-a205-42a9-b841-349874275018.png" style="white-space: normal;" />的DFA？

A、<img src="http://edu-image.nosdn.127.net/F3D46DF449653C02E14DAC4263F3505F.png?imageView&thumbnail=890x0&quality=100" style="white-space: normal;" />

B、<img src="http://edu-image.nosdn.127.net/3FC6066230463CA0EFF3CA647AB9E214.png?imageView&thumbnail=890x0&quality=100" style="white-space: normal;" />

C、<img src="http://edu-image.nosdn.127.net/76058F4E13F0CECC05C28EA17D5422F3.png?imageView&thumbnail=890x0&quality=100" style="white-space: normal;" />

D、<img src="http://edu-image.nosdn.127.net/1C19B34E0991F9FBBBAC5A27D1625F36.png?imageView&thumbnail=890x0&quality=100" style="white-space: normal;" />

E、<img src="http://edu-image.nosdn.127.net/AEB920CD459CF99BDF39C4A6A4809283.png?imageView&thumbnail=890x0&quality=100" style="white-space: normal;" />

10、【单选题】带有空转移的非确定有穷自动机中，对于某一个状态，是否可以同时存在“对某字符a的非确定性”和“空转移”？

A、可以。

B、不可以。

C、有空转移时可以有对某个字符a的非确定性，但反之不可以。

D、对某个字符a有非确定性时可以有空转移，但反之不可以。

11、【单选题】NFA处于某个状态q且输入某字符a时，如果状态转移函数未定义，则NFA会：

A、跳过该输入字符，继续运行。

B、停止自动机的运行，是否接受该字符串，由当前状态是否为终态决定。

C、停止自动机的运行，并接受该串。

D、停止自动机的运行，并拒绝该串。

12、【单选题】NFA的状态转移图如下，则其状态转移表为： <img src="http://edu-image.nosdn.127.net/B7D5B4E4F20AB93BB46EF99A2774E40B.png?imageView&thumbnail=890x0&quality=100" />

A、<img src="http://edu-image.nosdn.127.net/E4D881F57C7ED22A42B140FC18645AA0.png?imageView&thumbnail=890x0&quality=100" style="white-space: normal;" />

B、<img src="http://edu-image.nosdn.127.net/55DD2D7A69E69C9C361C88396CEA0BA6.png?imageView&thumbnail=890x0&quality=100" style="white-space: normal;" />

C、<img src="http://edu-image.nosdn.127.net/82ED4742FD4C7E52EA0AA76B6DF9B190.png?imageView&thumbnail=890x0&quality=100" style="white-space: normal;" />

D、<img src="http://edu-image.nosdn.127.net/37C0E8E3239A75FD95CA0C4E1AC36202.png?imageView&thumbnail=890x0&quality=100" style="white-space: normal;" />

13、【单选题】若NFA <img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_83d832bc-41ae-45ba-96e3-23a183986679.png" style="white-space: normal;" />，则其接受的语言的定义是：

A、<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_d75690cd-fe6f-4346-a1b7-d96bb667c41b.png" style="white-space: normal;" />

B、<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_29cc2fbe-42ea-4c56-a631-7ce480de98bb.png" style="white-space: normal;" />

C、<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_664fe4e8-d21d-4e48-959c-4668530f5bcf.png" style="white-space: normal;" />

D、<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_8dfec377-2587-48b1-8c4e-8327cd3740a4.png" style="white-space: normal;" />

14、【单选题】语言<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_af394a03-34f9-428a-82aa-bed2d8bcfc46.png" style="white-space: normal;" />的NFA是以下哪一个？

A、<img src="http://edu-image.nosdn.127.net/01291578C7F73FFAC1D4F82638CE0AFC.png?imageView&thumbnail=890x0&quality=100" style="white-space: normal;" />

B、<img src="http://edu-image.nosdn.127.net/290449AE538A47E3786E5CE6165C8099.png?imageView&thumbnail=890x0&quality=100" style="white-space: normal;" />

C、<img src="http://edu-image.nosdn.127.net/D3905C3AC066F4E9E37D44C868EEA39C.png?imageView&thumbnail=890x0&quality=100" style="white-space: normal;" />

D、<img src="http://edu-image.nosdn.127.net/38FEEEDA7A516F6DB682222E6E1EC779.png?imageView&thumbnail=890x0&quality=100" style="white-space: normal;" />

15、【单选题】利用子集构造法，构造与NFA <img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_d5be28d4-ec2c-479e-9b44-19be7fced42e.png" style="white-space: normal;" />等价的DFA <img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_2f6a8b5a-77d3-4272-a4f3-e68fe1263b62.png" style="white-space: normal;" />时，其中<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_983f5b02-6d57-4774-a658-fa9ad10b5e7e.png" style="white-space: normal;" />为

A、<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_49e2375b-bc01-498e-8fa8-acb591eae180.png" style="white-space: normal;" />

B、<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_83db8b35-c210-46a7-aeff-e8f746f2608e.png" style="white-space: normal;" />

C、<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_c94456ed-8fee-4227-9a39-8e642407315a.png" style="white-space: normal;" />

D、<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_1ad2daa9-5c72-400f-8af0-e4da1623bad3.png" style="white-space: normal;" />

16、【单选题】利用子集构造法，构造与NFA <img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_d5be28d4-ec2c-479e-9b44-19be7fced42e.png" style="white-space: normal;" />等价的DFA <img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_2f6a8b5a-77d3-4272-a4f3-e68fe1263b62.png" style="white-space: normal;" />时，对<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_a8bad0ab-10ef-4640-87ef-48ddb3a30255.png" style="white-space: normal;" />，<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_7408ea38-fc63-47e2-a51b-5c97b9b59523.png" style="white-space: normal;" />为

A、<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_58d314f2-81eb-4b6b-92f5-d5af881f3a00.png" style="white-space: normal;" />

B、<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_9f8e527c-3d9d-4115-b612-eb3ed68405d5.png" style="white-space: normal;" />

C、<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_5cdc6012-acfe-4552-8362-b0ff56780e00.png" style="white-space: normal;" />

D、<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_709e09ee-5ba5-4089-8b97-88e2af7c9fc6.png" style="white-space: normal;" />

17、【单选题】将如下转移图中的NFA转换为下面表格中的DFA时，表中的A处应该填入？NFA:<img src="http://edu-image.nosdn.127.net/CD46FA20036DB79690EA191B9B1C39B9.png?imageViewDFA:<img src="http://edu-image.nosdn.127.net/CB0719149BE881F9005C931A58B71313.png?imageView

A、<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_c3266511-637d-4091-a997-04826f0cd27b.png" style="white-space: normal;" />

B、<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_ce66240a-c5e7-45bc-90ae-59f5c1f32ef8.png" style="white-space: normal;" />

C、<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_b63571fc-edc7-453a-8f22-77070ca1d896.png" style="white-space: normal;" />

D、<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_8394867b-d593-4e5c-b897-ddb7c86e71d6.png" style="white-space: normal;" />

E、<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_557bac07-0b97-4cd1-950c-65070bc6ef25.png" style="white-space: normal;" />

F、<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_4c3bd2bc-4aeb-4931-be08-73dd09a7eea0.png" style="white-space: normal;" />

G、<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_64aa8396-5220-4edc-83bf-1653fdd8033b.png" style="white-space: normal;" />

H、<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_e084367d-2dd7-4e8d-8ca6-3eecb6372d36.png" style="white-space: normal;" />

I、<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_21a444f7-fd98-44a0-8823-b00b4f86c9ef.png" style="white-space: normal;" />

J、<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_48ccd148-8ad6-4f4a-95ff-e9940a545f0e.png" style="white-space: normal;" />

K、<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_d7e4b474-5998-4b45-90b9-7c0720a9d3af.png" style="white-space: normal;" />

18、【单选题】所有由0和1构成的字符串，或者由01重复一次或多次，或者由010重复一次或多次构成，其NFA为？

A、<img src="http://edu-image.nosdn.127.net/7EB30AD130C33DB5006529667D0ABAAF.png?imageView&thumbnail=890x0&quality=100" style="white-space: normal;" />

B、<img src="http://edu-image.nosdn.127.net/673700AB20AC847A39E810BA7C65267E.png?imageView&thumbnail=890x0&quality=100" style="white-space: normal;" />

C、<img src="http://edu-image.nosdn.127.net/737E81E7DE5ECFA645812E9DCACA5DB0.png?imageView&thumbnail=890x0&quality=100" style="white-space: normal;" />

D、<img src="http://edu-image.nosdn.127.net/5F1ED17988D595020C9E45906FDE22EB.png?imageView&thumbnail=890x0&quality=100" style="white-space: normal;" />

19、【单选题】下图的NFA中，状态<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_61389751-5cb9-4720-8c86-09cbcc18f726.png" />的闭包<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_378a578b-b16d-4813-bd56-8937d38ee35a.png" /><img src="http://edu-image.nosdn.127.net/6EC4BA6C7B6BCCBE5DAC49DD29756341.png?imageView

A、<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_8ccc4538-a583-4627-8367-6943a08b3ec2.png" style="white-space: normal;" />

B、<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_989222dc-fcf3-4a58-b2d0-cb6d8451242e.png" style="white-space: normal;" />

C、<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_c5c6e61c-2957-4579-9375-1c68a8d9ff4d.png" style="white-space: normal;" />

D、<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_3eeb7f6c-f4c5-4b45-97aa-638e4f220a75.png" style="white-space: normal;" />

20、【判断题】扩展转移函数<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_45f74226-a7ca-4a32-9a57-0e839bdf65f6.png" />必须从开始状态<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_5ca5c167-583a-44cb-a383-6c2c73631d57.png" />处理字符串吗?

A、正确

B、错误

21、【判断题】从某一个状态开始，对任意的串<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_44ce1fe5-ad58-40d6-8133-550657993b2a.png" />，经过扩展转移函数<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_90dd3f5b-fde6-48bb-bdb4-824998c56191.png" />，能保证一定会跳转到某个状态吗?

A、正确

B、错误

22、【判断题】有穷自动机有了非确定性, 增加了它识别语言的能力。

A、正确

B、错误

23、【判断题】有穷自动机有了空转移（不消耗输入串的状态跳转）, 改变了它识别语言的能力。

A、正确

B、错误

24、【判断题】对同一个语言，可能存在两个不同的有穷自动机识别。

A、正确

B、错误

25、【判断题】两个不同的有穷自动机可能识别同一个语言。

A、正确

B、错误

26、【判断题】NFA处于某个状态q且输入某字符a时，状态转移函数可以未定义的情况出现。

A、正确

B、错误

第3章测试正则表达式

1、【单选题】字母表{a,b,c}上包含至少一个a和至少一个b的串的集合，正则表达式为？

A、<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_850eaedb-067c-4b95-bc9d-eb363e730a09.png" />

B、<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_6ab4d769-549c-4b4b-9812-c878d6fc044a.png" />

C、<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_af309d40-57c2-4554-91f6-0a600df51900.png" />

D、<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_c48dddfb-02b5-4c27-b2f9-be16869bb457.png" />

2、【单选题】由0和1构成的字符串中，不含101子串的全部串，正则表达式为？

A、<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_ef0d6228-0727-4e18-9bfb-e6836eb6f76b.png" />

B、<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_f2740f8f-9b69-4355-b570-1ef385c9c5a0.png" />

C、<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_b4ce64a2-1de4-4c9c-aff1-4b1d9caa08bc.png" />

D、<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_94889a2b-c2a4-40c0-a01b-232e1f7b8204.png" />

E、<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_06b11d83-63a5-4a1e-9a0f-324ce0031e88.png" />

F、<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_3085185e-0c72-46ba-986f-1b1c79e9ca4c.png" />

3、【单选题】由数量相等的0和1构成的字符串，且串的任何前缀中，0的数量不比1多2个、1的数量也不比0多2个，正则表达式为？

A、<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_f646706b-37c2-440a-a4a2-f77af8495b7c.png" />

B、<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_4ce1b5e8-7d38-441f-8c03-0982b0e67c07.png" />

C、<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_77cf0781-ec2f-418c-8e17-0eb30f749423.png" />

D、<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_9934404f-1b77-4370-9500-b6b667aa340e.png" />

4、【单选题】正则表达式<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_c10489a5-dd62-4126-8a22-465f360f3a8e.png" />与以下哪个等价？

A、<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_48637153-1ed3-47fa-8c95-62466677f92a.png" />

B、<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_c8e97efa-acf6-4aeb-91f6-fe484f454959.png" />

C、<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_04763ec7-c01c-4152-bdb8-ae3260c29cdd.png" />

D、<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_f6cdd00f-8365-4126-ae1a-0195dd2944c1.png" style="white-space: normal;" />

5、【单选题】正则表达式<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_63f9b34a-457b-4eb1-9e9f-71d6e3ba19ab.png" />可化简为

A、<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_0b9ed03c-25cb-4f18-9661-af1cb156a605.png" />

B、<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_4bbd8341-09ba-4bb1-944a-443feb6c790c.png" />

C、<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_3d2b1c06-dce6-4400-9fb1-f6d31d25ab72.png" />

D、<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_73c94e32-b6f6-4820-8f17-b83d5a857af7.png" />

6、【单选题】正则表达式<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_6cca1acf-2210-4f7a-9523-3c0f26f46c35.png" />=？

A、<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_b946af19-55d3-4d9d-8053-6d19099fe954.png" />

B、<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_49deeed8-3058-4a4c-bec7-42312deb07f9.png" />

C、<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_0ac7c44b-0400-4b24-92f1-8d50c8d8b28c.png" />

D、<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_f68b87d1-79d1-4e4d-a7d7-48029054fe91.png" />

7、【单选题】由0和1构成的、至多有一对儿连续1的全部字符串，正则表达式为

A、<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_977d3114-5e29-42fc-b522-c7f1daa1476e.png" />

B、<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_1f1dbb41-1f10-42b7-be7e-5bb95934764a.png" />

C、<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_50eca5d9-63c4-49ab-8de5-6614de464589.png" />

D、<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_10a1108c-d5fb-4408-9601-761551531155.png" />

8、【单选题】利用递归式<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_c0bc67e9-a09f-4b8b-87c8-4ecdd45ee9df.png" />将下表DFA转换为正则表达式时，<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_c7f0093f-c920-4e56-81a6-0f619d35b2ee.png" /><img src="http://edu-image.nosdn.127.net/B67744D6A87FCA7AA2AD987CBEC56107.png?imageView&thumbnail=890x0&quality=100" />

A、<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_60447d73-92b8-45cd-a5c5-077a053426d8.png" />

B、<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_aab1547d-6678-4dcd-8212-b30537147ea8.png" />

C、<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_2616dd67-1121-4a58-9a7e-dac7ffc2fef2.png" />

D、<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_048c5c28-1f1a-4577-a2eb-9774020f5d21.png" />

E、<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_8107f692-707e-454e-ab49-e9ff9e189685.png" />

F、<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_61946a67-e5e8-44f3-9d02-6e964470d1a4.png" />

9、【单选题】正则表达式<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_5cf1f944-552f-47f1-a37c-59878abe4e12.png" />所定义的语言为？

A、由0和1构成的、没有连续1的字符串。

B、由0和1构成的、不以0开头的字符串。

C、由0和1构成的、由01和0构成的字符串。

D、由0和1构成的、以0结尾的字符串。

10、【单选题】正则表达式<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_55984709-78de-48f7-9739-f446e3fdaf6f.png" />所定义的语言为？

A、由0和1构成的、没有连续的 1 在 0 前的字符串。

B、由0和1构成的、只能以1结尾的字符串。

C、由0和1构成的、没有连续1的字符串。

D、由0和1构成的、不以1开头的字符串。

11、【判断题】设<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_4a306526-bf4a-40d1-b8b3-4a085ec523f7.png" />是字母表<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_74e49ced-51c3-4e3a-8a9f-19a12054f823.png" />上的任意语言，则语言<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_4a306526-bf4a-40d1-b8b3-4a085ec523f7.png" style="white-space: normal;" />的闭包<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_674bb6be-3d15-44d4-8270-a7ae59dce52d.png" />一定是无穷的。

A、正确

B、错误

12、【判断题】设<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_d17e8718-1fc5-4227-9e18-ef70263fa24c.png" />和<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_c59d174e-4b39-4877-a8b9-2db0a0d3bd20.png" />是字母表<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_74e49ced-51c3-4e3a-8a9f-19a12054f823.png" style="white-space: normal;" />上的任意语言且<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_d17e8718-1fc5-4227-9e18-ef70263fa24c.png" style="white-space: normal;" />是无穷的，则两个语言的连接<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_dae9cf68-384e-4a13-b778-83b838869471.png" />一定是无穷的。

A、正确

B、错误

作业1

第4章测试正则语言的性质

1、【单选题】有关正则语言的泵引理，以下描述正确的是：

A、如果一个语言是正则的，一定符合泵引理。

B、如果一个语言符合泵引理，一定是正则的。

C、有限的语言一定是正则的，但不符合泵引理。

D、无限的语言如果符合泵引理，一定是正则的。

E、无限的语言如果不符合泵引理，一定不是正则的。

F、无限的语言如果不符合泵引理，一定是正则的。

2、【单选题】泵引理中与某正则语言相关的正整数<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_6c7f8b51-bbf5-45f0-80c6-4a05aceccbe5.png" />，与识别该语言的DFA状态数<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_c44fa55a-e96b-4cfe-94b0-62c0e6ba3694.png" />之间的关系为？

A、<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_bf2b8adf-ea9d-4cf1-8c8c-26f18aff61d0.png" />

B、<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_f9555341-76de-4b1a-8300-1d548de99e8e.png" />

C、<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_b708dbeb-703a-4472-9673-9769c80ae21e.png" />

D、无关

3、【单选题】设同一字母表<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_1812d48e-c359-4ef2-9539-1ce80cca7b6f.png" />上的语言<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_c6372063-c545-426b-ab94-dcba0b9bcdc5.png" />和<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_23e99b45-47ad-4a6d-a53d-846c0f98e368.png" />，如果满足<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_c97b8b4b-cd82-4c81-95d6-ae68744df1b0.png" />，那么以下描述正确的是：

A、如果<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_2d71ae02-efde-4e8a-89d3-096acce7b486.png" />是正则的，则<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_e8d49b03-656e-420a-a3b1-15d73104b34a.png" style="white-space: normal;" />一定是正则的。

B、如果<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_2d71ae02-efde-4e8a-89d3-096acce7b486.png" />和<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_4f8b6ccc-a283-4d8e-a20f-18fbd07cf6c0.png" style="white-space: normal;" />都是正则的，则<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_e8d49b03-656e-420a-a3b1-15d73104b34a.png" />一定是正则的。

C、如果<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_2d71ae02-efde-4e8a-89d3-096acce7b486.png" />和<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_e8d49b03-656e-420a-a3b1-15d73104b34a.png" style="white-space: normal;" />都是正则的，则<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_4f8b6ccc-a283-4d8e-a20f-18fbd07cf6c0.png" style="white-space: normal;" />一定是正则的。

D、如果<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_e8d49b03-656e-420a-a3b1-15d73104b34a.png" />是正则的，则<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_2d71ae02-efde-4e8a-89d3-096acce7b486.png" style="white-space: normal;" />和<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_4f8b6ccc-a283-4d8e-a20f-18fbd07cf6c0.png" />至少有一个是正则的。

4、【单选题】设同一字母表<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_1812d48e-c359-4ef2-9539-1ce80cca7b6f.png" style="white-space: normal;" />上的语言<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_c6372063-c545-426b-ab94-dcba0b9bcdc5.png" style="white-space: normal;" />和<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_23e99b45-47ad-4a6d-a53d-846c0f98e368.png" style="white-space: normal;" />，如果满足<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_c97b8b4b-cd82-4c81-95d6-ae68744df1b0.png" style="white-space: normal;" />，那么以下描述正确的是：

A、如果<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_2d71ae02-efde-4e8a-89d3-096acce7b486.png" />和<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_4f8b6ccc-a283-4d8e-a20f-18fbd07cf6c0.png" />都不是正则的，则<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_e8d49b03-656e-420a-a3b1-15d73104b34a.png" />一定不是正则的。

B、如果<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_2d71ae02-efde-4e8a-89d3-096acce7b486.png" style="white-space: normal;" />是正则的，但<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_e8d49b03-656e-420a-a3b1-15d73104b34a.png" style="white-space: normal;" />不是正则的，则<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_4f8b6ccc-a283-4d8e-a20f-18fbd07cf6c0.png" style="white-space: normal;" />一定不是正则的。

C、如果<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_e8d49b03-656e-420a-a3b1-15d73104b34a.png" style="white-space: normal;" />不是正则的，则<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_2d71ae02-efde-4e8a-89d3-096acce7b486.png" style="white-space: normal;" />和<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_4f8b6ccc-a283-4d8e-a20f-18fbd07cf6c0.png" style="white-space: normal;" />一定都不是正则的。

D、如果<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_2d71ae02-efde-4e8a-89d3-096acce7b486.png" style="white-space: normal;" />是正则的，<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_4f8b6ccc-a283-4d8e-a20f-18fbd07cf6c0.png" style="white-space: normal;" />不是正则的，则<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_e8d49b03-656e-420a-a3b1-15d73104b34a.png" style="white-space: normal;" />一定不可能正则的。

5、【单选题】设同一字母表<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_1812d48e-c359-4ef2-9539-1ce80cca7b6f.png" style="white-space: normal;" />上的语言<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_c6372063-c545-426b-ab94-dcba0b9bcdc5.png" style="white-space: normal;" />和<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_23e99b45-47ad-4a6d-a53d-846c0f98e368.png" style="white-space: normal;" />，如果满足<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_35b6505d-564b-4026-8feb-06586660c9fa.png" />，那么以下描述正确的是：

B、如果<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_2d71ae02-efde-4e8a-89d3-096acce7b486.png" />和<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_e8d49b03-656e-420a-a3b1-15d73104b34a.png" style="white-space: normal;" />都不是正则的，则<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_4f8b6ccc-a283-4d8e-a20f-18fbd07cf6c0.png" style="white-space: normal;" />一定不是正则的。

C、如果<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_2d71ae02-efde-4e8a-89d3-096acce7b486.png" style="white-space: normal;" />是正则的，<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_e8d49b03-656e-420a-a3b1-15d73104b34a.png" style="white-space: normal;" />不是正则的，则<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_4f8b6ccc-a283-4d8e-a20f-18fbd07cf6c0.png" style="white-space: normal;" />一定不是正则的。

D、如果<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_2d71ae02-efde-4e8a-89d3-096acce7b486.png" style="white-space: normal;" />不是正则的，<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_e8d49b03-656e-420a-a3b1-15d73104b34a.png" style="white-space: normal;" />是正则的，则<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_4f8b6ccc-a283-4d8e-a20f-18fbd07cf6c0.png" style="white-space: normal;" />一定是正则的。

6、【单选题】设同一字母表<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_1812d48e-c359-4ef2-9539-1ce80cca7b6f.png" style="white-space: normal;" />上的语言<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_c6372063-c545-426b-ab94-dcba0b9bcdc5.png" style="white-space: normal;" />和<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_23e99b45-47ad-4a6d-a53d-846c0f98e368.png" style="white-space: normal;" />，如果满足<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_5a9f08aa-ee34-4c18-89f2-ff398940dbc8.png" />，那么以下描述正确的是：

A、如果<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_2d71ae02-efde-4e8a-89d3-096acce7b486.png" style="white-space: normal;" />不是正则的，<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_4f8b6ccc-a283-4d8e-a20f-18fbd07cf6c0.png" style="white-space: normal;" />是正则的，则<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_e8d49b03-656e-420a-a3b1-15d73104b34a.png" style="white-space: normal;" />一定不是正则的。

B、如果<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_2d71ae02-efde-4e8a-89d3-096acce7b486.png" style="white-space: normal;" />不是正则的，<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_e8d49b03-656e-420a-a3b1-15d73104b34a.png" style="white-space: normal;" />是正则的，则<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_4f8b6ccc-a283-4d8e-a20f-18fbd07cf6c0.png" style="white-space: normal;" />一定是正则的

C、如果<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_2d71ae02-efde-4e8a-89d3-096acce7b486.png" style="white-space: normal;" />和<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_4f8b6ccc-a283-4d8e-a20f-18fbd07cf6c0.png" style="white-space: normal;" />都不是正则的，则<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_e8d49b03-656e-420a-a3b1-15d73104b34a.png" style="white-space: normal;" />一定不是正则语言。

D、如果<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_2d71ae02-efde-4e8a-89d3-096acce7b486.png" style="white-space: normal;" />是正则，<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_e8d49b03-656e-420a-a3b1-15d73104b34a.png" style="white-space: normal;" />不是正则的，则<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_4f8b6ccc-a283-4d8e-a20f-18fbd07cf6c0.png" style="white-space: normal;" />一定不是正则的。

E、如果<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_2d71ae02-efde-4e8a-89d3-096acce7b486.png" style="white-space: normal;" />不是正则的，<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_4f8b6ccc-a283-4d8e-a20f-18fbd07cf6c0.png" style="white-space: normal;" />是正则的，则<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_e8d49b03-656e-420a-a3b1-15d73104b34a.png" style="white-space: normal;" />一定是正则的。

7、【单选题】使用泵引理证明某个语言是非正则的时候，有关该语言的正整数N是一个：

A、依赖于该语言的正整数常数。

B、与该语言无关的正整数常数。

C、依赖于该语言且大于特定值的变量。

D、与该语言无关且大于特定值的变量。

8、【单选题】使用泵引理证明某语言非正则的证明方法是：

A、反证法。

B、归纳法。

C、演绎法。

D、赋值法。

E、归谬法。

9、【判断题】每一个有穷的语言都是正则语言。

A、正确

B、错误

10、【判断题】每一个无穷的语言都不是正则语言。

A、正确

B、错误

11、【判断题】如果语言<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_4de59d75-9367-46fa-9dd0-d8f6a8695682.png" />不是正则的，则对每个<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_19fe823e-8a9b-4e69-805c-5b096a89c06e.png" />都有一个DFA接受<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_babbc46a-8f3a-4064-8c05-761702cc42cb.png" />。

A、正确

B、错误

12、【判断题】如果语言<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_17c3c7fb-c9cd-4501-a473-fbef0c32c7da.png" style="white-space: normal;" />是正则的，且<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_a092a3f3-8940-4e7b-adcf-a519b719e076.png" style="white-space: normal;" />，那么<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_2fbf3e99-3753-4026-81c6-a5557f57e4fb.png" style="white-space: normal;" />也是正则的。

A、正确

B、错误

13、【判断题】如果语言<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_17c3c7fb-c9cd-4501-a473-fbef0c32c7da.png" style="white-space: normal;" />是正则的，且<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_a092a3f3-8940-4e7b-adcf-a519b719e076.png" style="white-space: normal;" />，那么<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_2fbf3e99-3753-4026-81c6-a5557f57e4fb.png" style="white-space: normal;" />不是正则的。

A、正确

B、错误

14、【判断题】如果语言<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_317f0c4f-004e-4be6-b34b-fd0eb6ab20b8.png" />是正则的，则语言<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_6343f5d4-d6e7-490b-a3ea-748e6ffa499d.png" />也是正则的。

A、正确

B、错误

15、【判断题】语言<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_985f95da-cea3-4eb6-a075-8155c902f2eb.png" style="white-space: normal;" />不是正则语言。

A、正确

B、错误

第5章测试上下文无关文法

1、【单选题】由文法 <img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_a14fb25e-1d1e-44a4-ac4a-f9a69970e1c2.png" />，无法产生下面的哪个字符串？

A、100001

B、010010

C、110001000

D、001010100

2、【单选题】以下文法中那个是定义语言<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_018bb73e-41f5-4f31-b56f-97ea160d354d.png" />的文法。

A、<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_0dafa986-4f5b-459d-a19b-59d948386b93.png" />

B、<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_152e2817-afdf-40dd-9e30-fc8be831a4ba.png" />

C、<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_8c4310c7-94c2-4d78-89cb-5e567ab676a2.png" />

D、<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_414dd321-9c51-4d73-9410-2aac01ea8226.png" />

3、【单选题】以下哪个，是该文法定义的语言<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_3d666500-a5a4-414e-b920-0cba07cc8197.png" /><img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_07ec878d-0f48-4d34-b166-0c6c9cd42724.png" /><img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_dabfa464-ba50-4635-a6a0-e0bb46b518ba.png" />

A、<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_ae55d505-e218-4f91-87ad-1e1637bd23cf.png" />

B、由0和1构成且至少含有一个1的字符串的集合

C、由0和1构成且必须以0开头的字符串的集合

D、<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_e5765565-0490-42ed-953a-e83c47a810cb.png" style="white-space: normal;" />

E、<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_7a3f6fae-b6fe-4fe7-95ac-f99c3c1031c4.png" />

4、【单选题】若文法为<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_3d666500-a5a4-414e-b920-0cba07cc8197.png" /><img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_07ec878d-0f48-4d34-b166-0c6c9cd42724.png" /><img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_dabfa464-ba50-4635-a6a0-e0bb46b518ba.png" />，那么字符串 <img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_f7080c1f-5cb9-46fa-83cb-4ebf39caba98.png" /> 的最左派生（推导）为？

A、<img src="http://edu-image.nosdn.127.net/1AFD1B83D84480245D6A863F05DD1461.png?imageView&thumbnail=890x0&quality=100" />

B、<img src="http://edu-image.nosdn.127.net/2D9006F8C48D4FF0C75E17A6574CCA13.png?imageView&thumbnail=890x0&quality=100" />

C、<img src="http://edu-image.nosdn.127.net/05F940A36CBF7D7E48E3143D124F1BB5.png?imageView&thumbnail=890x0&quality=100" />

D、<img src="http://edu-image.nosdn.127.net/A7D2CB59264B5EF9510C48DA3D180FBE.png?imageView&thumbnail=890x0&quality=100" />

5、【单选题】若文法为<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_cedc3625-b412-4d05-bd9a-c30e944672aa.png" />，那么字符串 <img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_21884529-a33b-4ffd-8877-2197bb69daf3.png" /> 的语法分析树为？

A、<img src="http://edu-image.nosdn.127.net/96F8093396A4CAFC49173802521830A3.png?imageView&thumbnail=890x0&quality=100" />

B、<img src="http://edu-image.nosdn.127.net/429CA513ACEB81C7EEDC2F8313839910.png?imageView&thumbnail=890x0&quality=100" />

C、<img src="http://edu-image.nosdn.127.net/34FA916C9EB40778A202DFA903EDEF70.png?imageView&thumbnail=890x0&quality=100" />

D、<img src="http://edu-image.nosdn.127.net/591CF25D11F720E7AADF7DAF6FF31CB1.png?imageView&thumbnail=890x0&quality=100" />

6、【单选题】如果有产生式<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_91684d9b-351b-48bf-97c7-dd7cfe782a86.png" />且变元<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_f95100c1-67fd-4fed-8720-eb305fee48bf.png" />都是可空的，那么在消除空产生式的化简中，需要增加哪些产生式才能使语言保持等价？

A、<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_3cd53780-c7e6-43b8-9ccb-cd1357e40b84.png" />

B、<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_c1ef48c1-ec77-4c76-a995-8b14afff0f6c.png" />

C、<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_36e3efa7-0597-4f9a-a6cc-dc225e2dd0b1.png" />

D、<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_607c5aeb-1ca3-4915-8aec-7b3d16905e3b.png" />

7、【判断题】文法表示语言的能力与正则表达式等价。

A、正确

B、错误

8、【判断题】语言 <img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_c68565b0-ff00-4cff-b97b-73c0ae052ae7.png" />是上下文无关语言。

A、正确

B、错误

9、【判断题】语言 <img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_0fcc1a73-8b0a-4ca1-9781-e66170fe2fae.png" style="white-space: normal;" />是正则语言。

A、正确

B、错误

10、【判断题】任何有限的语言都是上下文无关语言。

A、正确

B、错误

11、【判断题】以下文法不是歧义的。<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_ad3cb1ed-c1dc-40ac-bdcb-02d046c8b845.png" /><img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_7e1e394c-9ed2-406f-9768-88d4f0afe738.png" /><img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_0ccd5cea-6eec-4228-b3ee-15e52d039683.png" />

A、正确

B、错误

第6章测试下推自动机

1、【单选题】假设<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_ba4e1ff6-9284-4349-868e-fa21b07ff162.png" />具有下列转移函数：<img src="http://edu-image.nosdn.127.net/25F01E7AB880AC8DC3157D0FBDAD7559.png?imageView那么，当输入串01时，从初始ID <img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_3ef04360-c6f2-4fff-8dba-2a0c13bb5445.png" />开始，可达的ID为？

A、<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_da0bdf07-3bab-41d8-91bc-4b54c96cb835.png" />

B、<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_52121fd0-9954-4008-8b2a-d6cd8ae3d200.png" />

C、<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_bba82b0d-05d4-42f1-8155-1d034a7b22f3.png" />

D、<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_5b7b40ac-aa90-477f-8b36-24399b6d8c41.png" />

E、<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_c73de7cd-9470-4bc9-9f54-f98188c793ae.png" />

F、<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_d612f635-c44d-4770-bfdf-e35463255d46.png" />

2、【单选题】如果将<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_00d7c221-9c81-4eeb-a309-29cb96bf13ef.png" />转换为CFG，其中某一条转移函数若为<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_8dae3a8b-6fc5-4d85-adde-f4dba3773eee.png" />则由此条转移函数得到的产生式包括：

A、<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_d0608d20-d7a1-41ac-b9f5-af9d53934f60.png" />

B、<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_c268b3b2-be32-461a-bf01-e6695426b7ce.png" />

C、<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_57d70919-0513-4825-8a9b-9b30f5a445f3.png" />

D、<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_7be81814-921f-412a-9303-8fce9086a386.png" />

E、<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_f8e53f00-4cdb-4500-8661-5b62043ec3a7.png" />

F、<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_9cb2c404-9ede-47a3-b930-c5d4e2768607.png" />

G、<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_07c89fb3-56ed-478b-a7d4-0a3c0f0a942f.png" style="white-space: normal;" />

3、【单选题】接受语言<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_f2462ab0-5a56-4bb1-8880-b020fbf75a9f.png" />的PDA为

A、<img src="http://edu-image.nosdn.127.net/884FC7C006C9DADE6C53D728EA35B4B3.png?imageView&thumbnail=890x0&quality=100" />

B、<img src="http://edu-image.nosdn.127.net/60AF72E60BA32632FDBD833E59F0E5C7.png?imageView&thumbnail=890x0&quality=100" />

C、<img src="http://edu-image.nosdn.127.net/8EC847FF7C8E58713394D7C847E6E0FF.png?imageView&thumbnail=890x0&quality=100" />

D、<img src="http://edu-image.nosdn.127.net/3A6728657758229D33108D2062513D18.png?imageView&thumbnail=890x0&quality=100" />

4、【判断题】语言<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_8ee33ef3-3686-4b20-af1c-8e16b840394f.png" style="white-space: normal;" />是一个DCFL。

A、正确

B、错误

5、【判断题】语言<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_924c6a36-9d15-4794-8b63-536fd2381df5.png" />不是DCFL.

A、正确

B、错误

6、【判断题】任何正则语言都是上下文无关语言。

A、正确

B、错误

第7章测试上下文无关语言的性质

1、【单选题】由某字母表<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_7d7bf000-c2f3-457f-9f1f-e5baf8b21be5.png" />中的字符构成的全部正则表达式的集合，也可以看做是一个语言，则该语言为：

A、上下文无关语言

B、正则语言

C、<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_27ce710a-9fe9-46b0-aa73-7b59f69b72f7.png" />

D、<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_c9c67217-7161-4d98-85ae-6b0fa21f3ee4.png" />

2、【判断题】如果一个CFG G的全部产生式均为<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_1e71ce31-dc44-4463-88bd-14d102fff31a.png" />或<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_46b7c9be-4d2d-45c9-95e9-d161e77d7227.png" />形式，其中<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_61ffa130-6e46-4704-a816-783853430e94.png" />是终结符串，那么L(G)一定是正则语言。

A、正确

B、错误

3、【判断题】任何有限的语言都是上下文无关语言。

A、正确

B、错误

4、【判断题】语言<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_b93c5446-ca0f-4929-929c-e04215627485.png" />是一个DCFL.

A、正确

B、错误

5、【判断题】语言<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_4a119c9e-5790-4e4f-b20a-384e0af0ff0a.png" />是CFL.

A、正确

B、错误

6、【判断题】语言<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_a7d1ace8-c732-4679-897d-edb3182385aa.png" />是CFL.