正则表达式（编译原理）

短命女 2022-08-23 08:57 275阅读 0赞

# 《编译原理》第三章习题 #

我们的教材是那本经典的“龙书”： **《Compiler: Principles, Techniques, and Tools》**

![1342705981_8232.png][]

灰常灰常喜欢小监老师的课，就是做作业的记忆太痛苦了。。。

## 3.3.2 试描述下列正则表达式定义的语言 ##

## 3.3.5 ##

**3) Comments, consisting of a string surround by /\* and \*/, without an intervening\*/, unless it is inside double-quotes (")**

**\[plain\]** [view plain][] [copy][view plain]

[![在CODE上查看代码片][CODE]][CODE_CODE] [![派生到我的代码片][ico_fork.svg]][ico_fork.svg 1]

1.  (\\/\\\*) (.\*^(\\/\\\*)) (“(.\*)”|ε) (.\*^(\\/\\\*)) (\\\*\\/)

## 3.4.1 给出识别练习3.3.2中各个正则表达式所描述的语言的状态转换图 ##

**1) a(a|b)\*a**

**![1342706265_6407.png][]**

**2) ((ε|a)b\*)\***

**![1342706299_7405.png][]**

**3)(a|b)\*a(a|b)(a|b)**

**![1342706618_5002.png][]**

**4)a\*ba\*ba\*ba\***

**![1342706665_1308.png][]**

**![1342706393_4212.png][]**

## **3.6.2 为练习3.3.5中的每一个语言设计一个DFA或NFA** ##

**Comments, consisting of a string surround by /\* and \*/, without an intervening\*/, unless it is inside double-quotes (")**

设计NFA如下:

![1342706470_4166.png][]

(感觉这个有些问题，不知道^可不可以用作转移条件。。。。)

## 3.6.5 给出如下练习中的NFA的转换表 ##

**1)练习3.6.3**

**![1342706930_4999.png][]**

**2)练习3.6.4**

**![1342706953_3766.png][]**

**3)图 2-6**

**![1342706987_4007.png][]**

## **3.7.1 将下列图中的NFA转换为DFA** ##

**1)图3-26**

**![1342707306_3850.png][]**

**2)图3-29**

**![1342775016_4841.png][]**

**![1342775113_1079.png][]**

**3)图3-30**

**![1342775258_7098.png][]**

**![1342775280_3383.png][]**

# **3.7.3 用算法3.23和3.20将正则表达式转换为DFA** #

**1) (a|b)\***   
由算法3.23得到NFA:

![1342775374_1479.png][]

由算法3.20得到DFA:

![1342775452_1264.png][]

**2) (a\*|b\*)\***   
由算法3.23得到NFA:

![1342775484_7564.png][]

由算法3.20得到DFA:

![1342775545_2255.png][]

**3) ((ε|a)b\*)\***  
由算法3.23得到NFA:

**![1342775580_5116.png][]**

由算法3.20得到DFA:

![1342775763_3279.png][]

此处可以看到 1） 2） 3）表示的语义是等价的，NFA可以有多种表示形式，但DFA是唯一的

**4)(a|b)\*abb(a|b)\***  
由算法3.23得到NFA:

![1342775822_6470.png][]

由算法3.20得到DFA:

![1342775904_5886.png][]

[1342705981_8232.png]: https://img-my.csdn.net/uploads/201207/19/1342705981_8232.png
[view plain]: http://blog.csdn.net/xiaowei_cqu/article/details/7764967#
[CODE]: https://code.csdn.net/assets/CODE_ico.png
[CODE_CODE]: https://code.csdn.net/snippets/149065
[ico_fork.svg]: https://code.csdn.net/assets/ico_fork.svg
[ico_fork.svg 1]: https://code.csdn.net/snippets/149065/fork
[1342706265_6407.png]: https://img-my.csdn.net/uploads/201207/19/1342706265_6407.png
[1342706299_7405.png]: https://img-my.csdn.net/uploads/201207/19/1342706299_7405.png
[1342706618_5002.png]: https://img-my.csdn.net/uploads/201207/19/1342706618_5002.png
[1342706665_1308.png]: https://img-my.csdn.net/uploads/201207/19/1342706665_1308.png
[1342706393_4212.png]: https://img-my.csdn.net/uploads/201207/19/1342706393_4212.png
[1342706470_4166.png]: https://img-my.csdn.net/uploads/201207/19/1342706470_4166.png
[1342706930_4999.png]: https://img-my.csdn.net/uploads/201207/19/1342706930_4999.png
[1342706953_3766.png]: https://img-my.csdn.net/uploads/201207/19/1342706953_3766.png
[1342706987_4007.png]: https://img-my.csdn.net/uploads/201207/19/1342706987_4007.png
[1342707306_3850.png]: https://img-my.csdn.net/uploads/201207/19/1342707306_3850.png
[1342775016_4841.png]: https://img-my.csdn.net/uploads/201207/20/1342775016_4841.png
[1342775113_1079.png]: https://img-my.csdn.net/uploads/201207/20/1342775113_1079.png
[1342775258_7098.png]: https://img-my.csdn.net/uploads/201207/20/1342775258_7098.png
[1342775280_3383.png]: https://img-my.csdn.net/uploads/201207/20/1342775280_3383.png
[1342775374_1479.png]: https://img-my.csdn.net/uploads/201207/20/1342775374_1479.png
[1342775452_1264.png]: https://img-my.csdn.net/uploads/201207/20/1342775452_1264.png
[1342775484_7564.png]: https://img-my.csdn.net/uploads/201207/20/1342775484_7564.png
[1342775545_2255.png]: https://img-my.csdn.net/uploads/201207/20/1342775545_2255.png
[1342775580_5116.png]: https://img-my.csdn.net/uploads/201207/20/1342775580_5116.png
[1342775763_3279.png]: https://img-my.csdn.net/uploads/201207/20/1342775763_3279.png
[1342775822_6470.png]: https://img-my.csdn.net/uploads/201207/20/1342775822_6470.png
[1342775904_5886.png]: https://img-my.csdn.net/uploads/201207/20/1342775904_5886.png