学编译原理的困惑

yrbill 发表于 2009-06-01 16:33

请问下
构造正规表达式 (aa|b)*| (a|bb)*所对应的状态最少的DFA。
1.请给出该正规式对应的NFA。.
2.使用子集构造法，将１中的NFA确定化。
3.将2中的DFA状态最小化。

这个何解
(aa|b)*| (a|bb)*
应该是包含aa或者bb(无数个)与(a或者bb)(无数个)的逻辑或关系吧

是一本教科书上看到的 ,但是教科书上没有答案,期待大家帮忙

cjaizss 发表于 2009-06-01 16:38

随便找本书看看regex的语法吧，《编译原理》里肯定有关于regex语法的讲解

norechang 发表于 2009-06-01 18:29

回复 #1 yrbill 的帖子

RE to NFA,
使用 Thompson's construction rule
NFA to DFA
使用 Subset construction algorithm
龍書裡頭有方法說明

cathyleung 发表于 2009-06-02 10:09

支持支持～

页: [1]

Chinaunix's Archiver

学编译原理的困惑

回复 #1 yrbill 的帖子