作者ju22 (分享)
看板RegExp
标题[问题] RE无法表达的字串!?
时间Sat Jan 17 09:53:10 2009
前几天看到一个介绍Regular Expression的网站
内容有提到一个范例
说像是
ab
aabb
aaabbb
aaaabbbb
.....
(有多少个a後面就要有多少个b)
这种字串是RE所无法表达的...
说数学上已经证明为不可行?
我也想不出来要怎麽用RE来表达..
有办法写出这种字串的re吗?
thanks!!
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 61.228.96.174
1F：→ janyfor:请问原PO有数学上的证明吗? 01/17 18:38
3F：→ LyinZ:但现在常用的 regex lib 和数学上的 regex 并不完全一样. 01/17 19:39
4F：→ LyinZ:不过你写的例子我还是想不出写法 XD 01/17 19:40
5F：推 LPH66:就我查资料是表示现行的 lib 里的语法和数学上的 regex 差别 01/18 02:03
6F：→ LPH66:仅有 back reference (即 \1 \2 那些东西) 01/18 02:03
7F：→ LPH66:不过这个例子似乎也找不出有重覆的字串可以用 \1 \2 等表示 01/18 02:03
8F：→ LPH66:这好像印证了我前几篇的猜测说加上 back reference 之後 01/18 02:04
9F：→ LPH66:能表示的东西落在 regular language 和 context-free 之间 01/18 02:04
10F：→ LPH66:(因为这东西是可以用 context-free 表示出来的) 01/18 02:05
12F：推 springman:前面的 pumping lemma 就是证明了.... 01/19 12:18
13F：推 nowar100:RE是CFG的子集，(01)^n已经在数学上证明不可能用re表示了 08/17 01:08
14F：→ nowar100:所以才会有turing machine来吃CFG用的 08/17 01:08
15F：推 LPH66:(偶然爬回来看到这个推文)楼上错了...吃CFG的是pushdown 10/09 03:38
16F：推 nowar100:谢谢楼上指正 我记错了 Orz|| (也是偶然爬回来XD) 10/13 16:39