首页 > 其他 > 详细

11.6 DFA最小化,语法分析初步

时间:2019-11-08 19:50:41      阅读:100      评论:0      收藏:0      [点我收藏+]

1.将DFA最小化:教材P65 第9题

 答:技术分享图片

 

2.构造以下文法相应的最小的DFA

S→ 0A|1B

A→ 1S|1

B→0S|0

 答:

S=0A+1B

=0(1S+1)+1(0S+0)

=01(S+ε)+10(S+ε)

=(01+10)(S+ε)

=(01+10)S+(01+10).

=(01|10)*(01|10)

NFA如下:

技术分享图片

 

 

 由NFA可得DFA状态转换矩阵如下:

 

 

0

1

A

{XAD}

{BE}

{CF}

B

{BE}

 

{ADY}

C

{CF}

{ADY}

 

D

{ADY}

{BE}

                    {CF}

 

 

 

 

 

 

 

DFA如下图所示

技术分享图片

 

 

I

{ABC}

{D}

 

{A}0->{B}

{B}0->

{C}0->{D}

{ABC}可区分,划分

 

不可区分

II

{A}{B}{C}

{D}

 

 

 

 

 

 

 

最小DFA如下:

技术分享图片

3.

给定如下文法 G[S]:

AB

→ aA | ? 

→ b | bB

给出句子aaab 的一个自上而下语法分析,回溯产生的原因是什么?

 

答:

S -> AB

S -> aAB

S -> aaAB

S -> aaaAB

S -> aaa?b

S -> aaab

 

原因:反复提取公共左因子

4.P100 练习4,反复提取公共左因子。,对文法进行改写。

答:

提取公共左因子得

S→C$

C→bA|aB

A→aD|bAA

D→ε|C

B→bE|aBB

E→ε|C

11.6 DFA最小化,语法分析初步

原文:https://www.cnblogs.com/dianshuizheng/p/11803288.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!