?▓中山大学本科生期末考试试卷?▓

中山大学本科生期末考试

考试科目：《编译原理》（A卷答案）

学年学期：2016学年第一学期

姓 名：

学 院/系：数据科学与计算机学院/软件工程学 号： 考试方式：闭卷

年级专业： 班 别：

考试时长：120分钟

警示 《中山大学授予学士学位工作细则》第八条：“考试作弊者，不授予学士学位。”

------------以下为试题区域，共九道大题，总分100分,考生请在答题纸上作答------------ 1. Write regular expressions for the following languages (8 points).

a) All strings over {0, 1} that do not contain consecutive zeros (4 points).

(0?1)*0?

b) All strings representing a nonnegative binary number (without leading zeros)

which is a multiple of 8 (4 points). 0 | 1(1|0)*000

2. Consider the following regular expression (17 points):

( a | b ) * a ( a | b )

a) Based on the Thompson Algorithm, construct the NFA from the above regular

expression (8 points).

?▓中山大学本科生期末考试试卷?▓

b) Convert the NFA into a DFA with minimum number of states (9 points). ?-closure({0}) = {0, 1, 2, 4, 7}

?-closure(move({0, 1, 2, 4, 7}, ‘a’)) = ?-closure({3, 8}) = {1, 2, 3, 4, 6, 7, 8, 9, 11} ?-closure(move({0, 1, 2, 4, 7}, ‘b’)) = ?-closure({5}) = {1, 2, 4, 5, 6, 7}

?-closure(move({1, 2, 3, 4, 6, 7, 8, 9, 11}, ‘a’)) = ?-closure({3, 8, 10}) = {1, 2, 3, 4, 6, 7, 8, 9, 10, 11, 13}

?-closure(move({1, 2, 3, 4, 6, 7, 8, 9, 11}, ‘b’)) = ?-closure({5, 12}) = {1, 2, 4, 5, 6, 7, 12, 13}

?-closure(move({1, 2, 4, 5, 6, 7}, ‘a’)) = ?-closure({3, 8}) = {1, 2, 3, 4, 6, 7, 8, 9, 11} ?-closure(move({1, 2, 4, 5, 6, 7}, ‘b’)) = ?-closure({5}) = {1, 2, 4, 5, 6, 7}

?-closure(move({1, 2, 3, 4, 6, 7, 8, 9, 10, 11, 13}, ‘a’)) = ?-closure({3, 8, 10}) = {1, 2, 3, 4, 6, 7, 8, 9, 10, 11, 13}

?-closure(move({1, 2, 3, 4, 6, 7, 8, 9, 10, 11, 13}, ‘b’)) = ?-closure({5, 12}) = {1, 2, 4, 5, 6, 7, 12, 13}

?-closure(move({1, 2, 4, 5, 6, 7, 12, 13}, ‘a’)) = ?-closure({3, 8}) = {1, 2, 3, 4, 6, 7, 8, 9, 11}

?-closure(move({1, 2, 4, 5, 6, 7, 12, 13}, ‘b’)) = ?-closure({5}) = {1, 2, 4, 5, 6, 7} NFA states {0, 1, 2, 4, 7} DFA state A a B B C ?▓中山大学本科生期末考试试卷?▓

{1, 2, 3, 4, 6, 7, 8, 9, 11} {1, 2, 4, 5, 6, 7} {1, 2, 3, 4, 6, 7, 8, 9, 10, 11, 13} {1, 2, 4, 5, 6, 7, 12, 13} B C D E D B D B E C E C

Minimized DFA：

3. Consider the following CFG (9 points):

S ? +SS | -SS | a

and the string +a-aa.

a) Give a leftmost derivation for the string (3 points).

S => +SS => +aS => +a-SS => +a-aS => +a-aa