我來試著硬拆好了 ※ 引述《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