这是一个正则语言吗

cjaizss

转化之后应该是
S->D
D->a
D->aA
D->bC
A->aE
A->bF
A->aD
A->bB
B->b
B->bA
B->aC
C->aF
C->aB
C->bD
E->a
F->b
这就是标准的3类文法

fineamy

看来不同的材料定义有所不同
只要产生式均具有下列形式：
A -> ω
A -> ωB
ω是一终结符号串，
其定义的语言就是正则语言。不必要求ω是一个终结符号。

[ 本帖最后由 fineamy 于 2008-11-11 15:08 编辑 ]

cjaizss

其实定义是一样的,我可以证明两者是等价定义

cjaizss

识别正则语言的最简单的方法是，当你发现可以用一个状态机来描述，则是正则语言；
正则语言和状态机等价

cjog

谢谢，dfa我找到了
       a        b
A     C        B
B     D        A
C     A        D
D     B        C

A是start state,B是accepting state

[ 本帖最后由 cjog 于 2008-11-12 16:27 编辑 ]

flw2

肯定是正则语言,  一看很明显, 它要记忆的状态是有限的
但是根据书中的例子, 花了一中午没搞出来RE怎么写

大家给写写

fineamy

设 r1 = (aa)*
    r2 = (bb)*
    r3 = (abab)*
    r4 = (baba)*
于是
   r = ((r1)*(r2)*(r3)*(r4)*)*a

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

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

cjaizss

好象不是每个dfa都可以转为regex.中午试着证明一下

fineamy

r = (r1r2r3r4)*a

这样对应的文法可以是：

G :
S -> A
A -> BCDEa
B -> Baa | ε
C -> Cbb | ε
D -> Dabab | ε
E -> Ebaba | ε

正则文法也可以写出来：
G:
S -> A
A -> Ba
A -> Ca
A -> Da
A -> Ea
B -> Baa | ε
C -> Cbb | ε
D -> Dabab | ε
E -> Ebaba | ε

用的是由线性文法，左线性文法感觉不太好写，写出来应该就是cjaizss 那样

fineamy

有证明正则式都可以有FA表示，反过来，应该也是可以的

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