作者janyfor (你哪位ㄚ)
看板RegExp
标题Re: [问题] RE无法表达的字串!?
时间Wed Mar 25 14:22:53 2009
※ 引述《ju22 (分享)》之铭言：
: 前几天看到一个介绍Regular Expression的网站
: 内容有提到一个范例
: 说像是
: ab
: aabb
: aaabbb
: aaaabbbb
: .....
: (有多少个a後面就要有多少个b)
: 这种字串是RE所无法表达的...
: 说数学上已经证明为不可行?
: 我也想不出来要怎麽用RE来表达..
: 有办法写出这种字串的re吗?
: thanks!!
Pumping lemma
Let L be a regular language. Then there exist a const n such for every string
w in L such that |w| ≧ n, we can break w into three string, w = xyz,
such that :
1. y≠ε
2. |xy| ≦ n
3. For all k ≧ 0, the string xy^kz is also in L
L = {a^nb^n | n ≧ 1}
w = a^nb^n
= xyz
x = a^i
y = a^j
z = a^(n-i-j)b^n (i+j) ≦ n and j ﹥0
k = 0,
xy^kz = xy^0z
= xz
= a^ia^(n-i-j)b^n
= a^(n-j)b^n
j ≧ 1, (n-j)≠n => xy^0z is not in L
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 140.117.168.73
※ 编辑: janyfor 来自: 140.117.168.73 (03/25 14:24)