我来试着硬拆好了 ※ 引述《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