这是一个正则语言吗

baohuaihuai

原帖由 fineamy 于 2008-11-13 11:14 发表
设 r1 = (aa)*
    r2 = (bb)*
    r3 = (abab)*
    r4 = (baba)*
于是
   r = ((r1)*(r2)*(r3)*(r4)*)*a

((r1)*(r2)*(r3)*(r4)*)*是所有双数个数a,b形成的串，最后补一个a

abb?

fineamy

这是个ε-NFA，可以看到这几个路径形成的串均是可接受串。
Dεa              a
DAεaa          (aa)*aaa
DAεbb          (aa)*abb
DABεb          (aa)*a(bb)*bb
DABCεab      (aa)*a(bb)*b(aa)*aab
DABCDεa      (aa)*a(bb)*b(aa)*a(bb)*ba
DCεab           (bb)*bab
DCBεb          (bb)*b(aa)*ab
DCBAεbb       (bb)*b(aa)*a(bb)*bbb
DCBAεaa       (bb)*b(aa)*a(bb)*baa
DCBADεa      (bb)*b(aa)*a(bb)*b(aa)*aa

上面加起来就是这个DFA所识别的所有串

[ 本帖最后由 fineamy 于 2008-11-13 14:36 编辑 ]

fineamy

r1              (r12r13)*a
r2          (r12r13)*(aa)*aaa
r3          (r12r13)*(aa)*abb
r4          (r12r13)*(aa)*a(bb)*bb
r5      (r12r13)*(aa)*a(bb)*b(aa)*aab
r6     (r12r13)*(aa)*a(bb)*b(aa)*a(bb)*ba
r7           (r12r13)*(bb)*bab
r8         (r12r13)*(bb)*b(aa)*ab
r9       (r12r13)*(bb)*b(aa)*a(bb)*bbb
r10      (r12r13)*bb)*b(aa)*a(bb)*baa
r11      (r12r13)*(bb)*b(aa)*a(bb)*b(aa)*aa

r12   ((aa)*a(bb)*b(aa)*a(bb)*b)*
r13   ((bb)*b(aa)*a(bb)*b(aa)*a)*

最终结果：
r = r1 + r2 + r3 + r4 + r5 + r6 + r7 + r8 + r9 + r10 + r11

[ 本帖最后由 fineamy 于 2008-11-13 17:34 编辑 ]

fineamy

应该这样

r = ((r1)*(r2)*(r3)*(r4)*)*a((r1)*(r2)*(r3)*(r4)*)*

cjaizss

恩,确实有严格的数学证明：regex,dfa,3-type language三者等价

[ 本帖最后由 cjaizss 于 2008-11-13 15:31 编辑 ]

fineamy

当然可以写出来.
S->D
D->a
D->aA
D->bC
A->aa
A->bb
A->aD
A->bB
B->b
B->bA
B->aC
C->ab
C->aB
C->bD

实际上可以去掉
A->aa
A->bb
C->ab

cjaizss

S->D
D->a
D->aA
D->bC
A->aD
A->bB
B->b
B->bA
B->aC
C->aB
C->bD
不可去,这样无法生成aaa

[ 本帖最后由 cjaizss 于 2008-11-13 22:52 编辑 ]

fineamy

的确。
否则aaa,babbb,abaab将无法生成。

victorgreat

我是新人，哈哈～

nmap

眼花缭乱啊，正则表达式，DFA，
对了，龙书上面的一些正则表达式的题目也是好难啊，