推 LyinZ:aba 裡的 a 不是就不連續了? 04/19 20:20
推 giacch:/aa+b(bb)*aa+/ 04/19 20:43
※ 編輯: shingoliang 來自: 220.134.25.16 (04/19 21:18)
推 LPH66:/((aa)*b(bb)*)*/ 04/20 00:47
→ LPH66:唔等等... 04/20 00:47
→ LPH66:它可以弄出DFA 沒道理寫不出regexp...@_@ 04/20 00:48
推 freesamael:我也是想到先畫DFA耶，比較好思考 04/20 00:50
推 giacch:/(aa)*b(bb)*(aa)+|(aa)+b(bb)*|a(aa)*b(bb)*a(aa)*/ 04/20 09:32
→ giacch:啊... 我給的是有連續的... XD 04/20 09:35
→ giacch:一直給錯東西, 真是抱歉... orz 04/20 19:49
→ shingoliang:不會啦，謝謝:P 04/20 20:42
> -------------------------------------------------------------------------- <
作者: LPH66 (IWH68S0XZ8M89) 看板: RegExp
標題: Re: [問題] 連續a跟奇數b..
時間: Sun Apr 20 01:19:22 2008
※ 引述《shingoliang (那個冬天..是永恆)》之銘言：
: 抱歉不是連續，不好意思
: 請問怎麼表示偶數個a跟奇數個b的任意組合呢？
: 如aabbb、aba等等，想了很久，想不到如何可以完整表達，
: 在此先謝過~~
這玩意建DFA是秒殺
a
┌──┐
↘↓ a │
┌─○─→○←┐
b│ ↑ │ │b
│ b│ ↓b │
└→◎←─○─┘
│ a ↑
└──┘
a
但從這個DFA轉出來的regexp卻囧得跟什麼一樣:
(a(bb)*a)*(b|ab(bb)*a)((a(bb)*a)*|(b|ab(bb)*a)(a(bb)*a)*(b|ab(bb)*a))*
原PO如果要用的話就把這串拿去試吧 @_@
(我目前想不到短一點的表示法了...
要我直接解釋這一長串我也想不到 orz)
--
試著去對原PO舉的兩個例子:
aabbb: (a(bb)*a)*(b|ab(bb)*a)((a(bb)*a)*|(b|ab(bb)*a)(a(bb)*a)*(b|ab(bb)*a))*
[ aa ][b] [ bb ]
aba: (a(bb)*a)*(b|ab(bb)*a)((a(bb)*a)*|(b|ab(bb)*a)(a(bb)*a)*(b|ab(bb)*a))*
[ ε ] [ab a][ ε ]
--
[LPH] Oops, your OOP's a problem? 說:
你現在還是看不到狗?
************* 說:
看得到 只是 他們不會跑 就一直呆呆在那邊 一直在起點
[LPH] Oops, your OOP's a problem? 說:
你要按"ㄅㄧㄤˋ"它們才會跑啊@@"
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.112.30.84
推 freesamael:突然想起過去在修自動機理論的日子了XD 04/20 01:28
→ LPH66:就是上學期修過印象還很深XD 04/20 03:58
推 shingoliang:謝謝我看一下,我是只畫得出DFA,Reg太複雜弄不出來orz 04/20 15:39
※ 編輯: LPH66 來自: 140.112.30.84 (04/20 18:21)
→ giacch:我發現單個 b 會過... 的樣子..? (沒自信 = = 04/20 19:56
推 shingoliang:單個b可以阿~~ 04/20 20:42
→ giacch:嗯... 我誤以為要有a有b... 呵呵~ 04/20 21:03
> -------------------------------------------------------------------------- <
作者: shingoliang (那個冬天..是永恆) 看板: RegExp
標題: Re: [問題] 連續a跟奇數b..
時間: Sun Apr 20 15:54:40 2008
: --
: 試著去對原PO舉的兩個例子:
:
: aabbb: (a(bb)*a)*(b|ab(bb*)a)((a(bb)*a)*|(b|ab(bb*)a)(a(bb)*a)*(b|ab(bb*)a))*
: [ aa ][ b ] [ bb ]
:
: aba: (a(bb)*a)*(b|ab(bb*)a)((a(bb)*a)*|(b|ab(bb*)a)(a(bb)*a)*(b|ab(bb*)a))*
: [ ε ] [ab a][ ε ]
比較好奇的是這邊...
(b|ab(bb*)a)
應該是b 或者 ab(bb*)a ，應該寫成ab(bb)*a?? 不然bb*至少一定有一個b吧？
就會變成abba @@"
當時助教隨意解沒解出來，他提供了個想法：
兩個都偶再配一個b
(ε|aabb|abab|abba|bbaa|baba|baab ) assume 為 A
Reg: A*bA*
不過這例子沒包含到aba、abbba、aabaa、aaaabbbaa、abaabba等等格式，
後來直接想實在想不到 orz
而且沒教DFA轉REG方法，所以...
--
河豚は食いたし命はおしし....
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 122.126.4.129
※ 編輯: shingoliang 來自: 122.126.4.129 (04/20 15:55)
推 LPH66:囧 我打錯了 那裡應該是(b|ab(bb)*a) 04/20 18:20
→ LPH66:等等我回一篇試著拆的解釋法好了 04/20 18:20
> -------------------------------------------------------------------------- <
作者: LPH66 (IWH68S0XZ8M89) 看板: RegExp
標題: Re: [問題] 連續a跟奇數b..
時間: Sun Apr 20 18:57:13 2008
我來試著硬拆好了
※ 引述《LPH66 (IWH68S0XZ8M89)》之銘言：
: (a(bb)*a)*(b|ab(bb)*a)((a(bb)*a)*|(b|ab(bb)*a)(a(bb)*a)*(b|ab(bb)*a))*
整個式子是 R*G(R*|GR*G)* 的結構
表示整個式子相當於拆成用G分隔的段
然後第一個G抓住前面的一堆R (R*G)
後面兩個G一組 抓住其中的一堆R (GR*G)
在組與組之間的一堆R則由R*抓住
(也就是式子表示為一堆R和G的組合 其中G有奇數個
從後面兩個兩個G一組拆開)
從字串本身來看的話 我們可以照字串中兩個a一組 中間劃分開來
(因為一個R或一個G有0或2個a 而由於a有偶數個 必然不會有落單的)
例如: aaaaabbbbaaaaaabbbaaa => aa aa abbbba aa aa abbba aa
abbbbbaaababa => abbbbba aa b aba
aabbbbbaaaaabbbba => aa bbbbb aa aa abbbba
abbabbaba => abba bb aba
abababababa => aba b aba b aba
然後 把所有是兩個a之中有偶數個b的部份代換成R 其他的代換成G
由於b有奇數個 而代換成R的部份必然一共用去了偶數個b
因此剩下的b有奇數個 然後也只剩下了 (1)連續奇數個b (2)兩個a中間有奇數個b
因此代換成一個G的一段必然有奇數個b 因此全部必然有奇數個G
正好符合上面所提到的型式 (全部有奇數個G 兩兩間有0或多個R)
於是R就是(a(bb)*a) G就是(b(bb)*|ab(bb)*a)
之所以上面的G是(b|ab(bb)*a)的理由是取奇數個b一組和取一個b一組是一樣的
這相當於上面的分組中把只有一串b的拆成一個b一段
例如: aabbbbbaaaaabbbba => aa b b b b b aa aa abbbba
abbabbaba => abba b b aba
這樣G仍然會是奇數個
由於所有這樣的字串這樣拆完再代換完必然是如此型式
所以就可以用上面的R,G表示 把R,G代入對應字串就得到原式
反之不合的這樣拆必然出問題
---
這樣一分析的話
就可以得到另一種稍微直覺的寫法:
RG組合,G奇數個 可以寫成 R*GR*(GR*GR*)*
這樣就成了
(a(bb)*a)*(b|ab(bb)*a)(a(bb)*a)*((b|ab(bb)*a)(a(bb)*a)*(b|ab(bb)*a)(a(bb)*a)*)*
比上一個稍長 但仍然符合要求
--
'You've sort of made up for it tonight,' said Harry. 'Getting the
sword. Finishing the Horcrux. Saving my life.'
'That makes me sound a lot cooler then I was,' Ron mumbled.
'Stuff like that always sounds cooler then it really was,' said
Harry. 'I've been trying to tell you that for years.'
-- Harry Potter and the Deathly Hollows, P.308
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.112.30.84
推 shingoliang:太感謝了,真題真複雜,我仔細研究,thanks~~ 04/20 19:07