华南师范大学 编译原理期末复习整理 pdf例题

正则表达式：

例2.1 在仅由字母表中的3个字符组成的简单字母表∑={a, b, c}中，考虑在这个字母表上的仅包括一个b的所有串的集合。

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

例2.2 在与上面相同的字母表中，如果集合是包括了最多一个b的所有串。

( a | c )* b? ( a | c )*

DFA：

例2.6 串中仅有一个b的集合的正则表达式对应的DFA为？

例2.8 科学表示法的数字常量的正则表达式为： nat = [0-9]+

signedNat = (+|-)? nat

number = signedNat(“.” nat)? (E signedNat)? 如何画对应的DFA？

解：先设digit = [0-9]，sig = (+|-)，得：

例2.9 非嵌套注释的DFA描述。Pascal注释{ ( ~} )* }对应的DFA为：

C注释 /* ...( */不同时出现 )... */ 的DFA为：

NFA：

例2.12 根据Thompson方法将正则表达式 ab|a转换为NFA。

例2.13 利用Thompson方法画出正则表达式letter(letter| digit)*对应的NFA。

例2.14 与正则表达式a*相对应的NFA为：

NFA转DFA：

例2.15 将下面的NFA转换为DFA：

解：

例2.16 将下面的NFA转换为DFA：

解：

例2.17 正则表达式letter(letter| digit)*对应的NFA转换成DFA：

解：

DFA最小化：

例2.18 将与正则表达式letter(letter| digit)*相对应的DFA最小化：（08级的大三第二学期考这道）