正则表达式Regular Expression

发布时间：2020-12-14 04:35:53 所属栏目：百科来源：网络整理

导读：《编译原理》第三章习题我们的教材是那本经典的“龙书”：《Compiler: Principles,Techniques,and Tools》灰常灰常喜欢小监老师的课，就是做作业的记忆太痛苦了。。。 3.3.2 试描述下列正则表达式定义的语言 1) a(a|b)*a 以a开头且以a结尾，中间由零个或

《编译原理》第三章习题

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

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

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 
     
 (/*)(.*^(/*))(“(.*)”|ε)(.*^(/*))(*/)

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

1) a(a|b)*a

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

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

4)a*ba*ba*ba*

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

Comments,unless it is inside double-quotes (")

设计NFA如下:

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

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

1)练习3.6.3

2)练习3.6.4

3)图 2-6

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

1)图3-26

2)图3-29

3)图3-30

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

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

由算法3.20得到DFA:

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

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

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

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

转载请注明出处：http://www.52php.cn/article/p-swdvdxra-vo.html

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!