c***y
发帖数: 180 | 1 【 以下文字转载自 Mathematics 讨论区 】
【 原文由 cocoy 所发表 】
L = { uww'v | u,v,w 均属于(0,1)+ }w'是w的reverse
比如w=1101then w'=1011
直观上来说， DFA没法记住无限长的w，
所以L肯定不是一个regular language
但是怎么证明呢？用pumping lemma?
困难在于对了串x，使用pumping lemma构造的新的x'
由于u,v的选择不同，总是可以也满足L的条件，推不出矛盾来 | b*****l
发帖数: 114 | 2 L is regular
because for any consecutive 0s or 1s,e.g. 00, 11,
we can just regard w as the first 0 (or 1), and w' the second.
Also, we can prove that for any string without consecutive 0 or 1,
i.e. (10)+ or (01)+ , we can't represent it as ww',
So, L={ bit string s , s.t. s contains more than or equal to four
bits and s contains consecutive 0 or 1 in the substring(2,length-1)} | c***y
发帖数: 180 | 3 原来如此，难怪我推不出矛盾来，多谢指点
【在 b*****l 的大作中提到】
: L is regular
: because for any consecutive 0s or 1s,e.g. 00, 11,
: we can just regard w as the first 0 (or 1), and w' the second.
: Also, we can prove that for any string without consecutive 0 or 1,
: i.e. (10)+ or (01)+ , we can't represent it as ww',
: So, L={ bit string s , s.t. s contains more than or equal to four
: bits and s contains consecutive 0 or 1 in the substring(2,length-1)}
| r*******n
发帖数: 51 | 4 buptzwl,老兄现在研究什么啊？好高深啊！
哈哈。。。。
佩服佩服。。。
【在 b*****l 的大作中提到】
: L is regular
: because for any consecutive 0s or 1s,e.g. 00, 11,
: we can just regard w as the first 0 (or 1), and w' the second.
: Also, we can prove that for any string without consecutive 0 or 1,
: i.e. (10)+ or (01)+ , we can't represent it as ww',
: So, L={ bit string s , s.t. s contains more than or equal to four
: bits and s contains consecutive 0 or 1 in the substring(2,length-1)}
|
|
