这是一个正则语言吗

cjog

字母表包含a和b两个字母，由所有包含单数个a和双数个b的串所组成的语言是正则语言吗？我感觉不是，但不能给出证明，急盼高人指点，先行谢过

freearth

是正则语言。

原帖由 cjog 于 2008-11-10 17:00 发表
字母表包含a和b两个字母，由所有包含单数个a和双数个b的串所组成的语言是正则语言吗？我感觉不是，但不能给出证明，急盼高人指点，先行谢过

cjog

谢谢，请问它的正则表达式是什么呢

cjaizss

是正则语言,因为可以拿一个有限状态机描述出来.

cjaizss

如下:


                    a
双a双b  <  --------
            a            |
start --------->单a双b
|      ^              |     ^
|b    |               |      |
|       | b           |b    |b
v      |       a     V      |
双a单b   -------->单a单b
            <--------
                 a

[ 本帖最后由 cjaizss 于 2008-11-11 12:38 编辑 ]

fineamy

字母表包含a和b两个字母，由所有包含单数个a和双数个b的串所组成的语言是正则语言吗？我感觉不是，但不能给出证明，急盼高人指点，先行谢过

按LZ意思,可以构造出下列文法:

G: S -> BA
    A -> Ca
    B -> bbB |  ε         //如果双数不包括0个，那么去掉 ε  
    C -> aaC  | ε

显然文法是同时含有左线性和右线性文法，因此不是正则文法。
另外可以看出A,B产生式互相没有什么关系，因此是上下文无关语言，也就不是正则语言了。正则语言要上下文有关的。

该串表达式可以表示为((bb(bb)n)* + (aa(aa)m)*a)* +  (bb(bb)n)* + (aa(aa)m)*a    (n>=0,m>=0)，显然这里，m,n根本就没啥关系，很明显不是正则式。

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

fineamy

不好意思，对LZ的问题理解有误，
仔细一看，看来LZ的问题还不是那么简单
我上面我只给出了一种简单的情形，只可以识别诸如
bba,bbaaa,bbaaaaa,bbbbbba,....aaa,aaaaa....等串，
下列这样的串：
abababb,aabbabb,abbabba,babbaba,....
这些串也是满足要求的串。
看来还是不容易的。不过可以肯定，这样的串绝不是一个简单的正则文法所能描述的。

cjaizss

当然可以写出来.
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

fineamy

不错，ε-NFA。呵呵，想了半天，也不知道怎么描述。

cjaizss

原帖由 cjaizss 于 2008-11-11 12:35 发表
当然可以写出来.
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

可以看出来,该语言应该是一个正则语言;
正则语言的意思是首先是一个图灵语言(假设初始符号为S),
每条规则左边都只一个非结束符号,
除了S->ε之外,
所有其他的右边要么是一个结束符号,要么是一个结束符号接一个非结束符号.
所以上面写的还不是最后的正则语言的文法格式,应该再转化一下.