?▓中山大学本科生期末考试试卷?▓
中山大学本科生期末考试
考试科目：《编译原理》（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