→ janyfor:請問原PO有數學上的證明嗎? 01/17 18:38
→ LyinZ:但現在常用的 regex lib 和數學上的 regex 並不完全一樣. 01/17 19:39
→ LyinZ:不過你寫的例子我還是想不出寫法 XD 01/17 19:40
推 LPH66:就我查資料是表示現行的 lib 裡的語法和數學上的 regex 差別 01/18 02:03
→ LPH66:僅有 back reference (即 \1 \2 那些東西) 01/18 02:03
→ LPH66:不過這個例子似乎也找不出有重覆的字串可以用 \1 \2 等表示 01/18 02:03
→ LPH66:這好像印證了我前幾篇的猜測說加上 back reference 之後 01/18 02:04
→ LPH66:能表示的東西落在 regular language 和 context-free 之間 01/18 02:04
→ LPH66:(因為這東西是可以用 context-free 表示出來的) 01/18 02:05
推 springman:前面的 pumping lemma 就是證明了.... 01/19 12:18
> -------------------------------------------------------------------------- <
作者: 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)
> -------------------------------------------------------------------------- <
作者: evernever (Never) 看板: RegExp
標題: Re: [問題] RE無法表達的字串!?
時間: Thu Oct 8 20:49:44 2009
※ 引述《ju22 (分享)》之銘言：
: 前幾天看到一個介紹Regular Expression的網站
: 內容有提到一個範例
: 說像是
: ab
: aabb
: aaabbb
: aaaabbbb
: .....
: (有多少個a後面就要有多少個b)
: 這種字串是RE所無法表達的...
: 說數學上已經證明為不可行?
: 我也想不出來要怎麼用RE來表達..
: 有辦法寫出這種字串的re嗎?
: thanks!!
小弟在 PHP 上試出來了...在此跟大家分享
<?php
preg_match_all("/^(a(?1)?b)$/","aabb",$matches);
print_r($matches);
?>
手邊可以跑 PHP 的大大可以測試一下...
ˇ ab
ˇ aabb
ˇ aaabbb
ㄨ aab
ㄨ abb
ㄨ aaabb
.
.
.
如有 bug 歡迎討論 ...
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 203.158.50.103
推 LPH66:原來是用了遞迴的 pattern.... 10/09 03:45
→ LPH66:給不知道的人的連結 10/09 03:46
→ LPH66:那這樣這系列的語法能表示的字串又多很多了@_@ 10/09 03:47
推 cutecpu:推樓上給的補充說明 10/09 07:49
推 bibo9901:推原po和1樓 10/09 13:39
推 janyfor:真酷~~遞迴很像是硬幹幹出來的 @@" 其他語言有支援嗎?? 10/09 16:33
推 lg31cm:perl有類似的能力,其他就很難說了 10/11 02:58
→ lg31cm:問題是這樣炫技的成份大於實用性~ 10/11 02:59