Re: [問題] RE無法表達的字串!?
※ 引述《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)
討論串 (同標題文章)