Re: [閒聊] regular expression高手進來

看板Marginalman作者soulgem (あたしって、ほんとバカ)時間8年前 (2017/04/16 09:04)推噓5(5推 0噓 2→)

留言7則, 7人參與討論串4/4 (看更多)

※ 引述《pandix (麵包屌)》之銘言： : give regular expressions for the following languages on sigma = {a,b,c}: : (c)All strings that contain at least one occurrence of each symbol in sigma. : 我寫 (a+b+c)*(baa*c+caa*b+abb*c+cbb*a+acc*b+bcc*a)(a+b+c)* : 結果錯了 : 求解 : 救命啊想法是這樣... 從 sigma0 = {a,b} 開始... 要有 a b 至少各一個應該會寫成... aa*b(a+b)* or bb*a(a+b*) 如此一來如果是 a 開頭, 後面連幾個 a 隨便, 只要之後有個 b 後面就不管了. 對 b 開頭也一樣. --- 所以 sigma = {a,b,c} 的場合也是一樣看哪個先出現... 會變成這樣... aa*b(a+b)*c(a+b+c)* or aa*c(a+c)*b(a+b+c)* or bb*a(a+b)*c(a+b+c)* or bb*c(b+c)*a(a+b+c)* or cc*a(a+c)*b(a+b+c)* or cc*b(b+c)*a(a+b+c)* 簡單來說就是先出現 a 再出現 b 最後出現 c 或是其它種組合. 而且每個合法字串應該都只會合其中一種. --- Ex: aaaabcccc, abbbbabababc 1. (a+b+c)*(baa*c+caa*b+abb*c+cbb*a+acc*b+bcc*a)(a+b+c)* 前面的 (a+b+c)* 吃掉所有 abc 組合字串, 後面 pattern 沒機會對到... 所以用這個對效能會很悲劇 XD 2. （ a(a+b+c)*b(a+b+c)*c + a(a+b+c)*c(a+b+c)*b + b(a+b+c)*a(a+b+c)*c + b(a+b+c)*c(a+b+c)*a + c(a+b+c)*a(a+b+c)*b + c(a+b+c)*b(a+b+c)*a ）(a+b+c)* 這個好像會很混雜... 中間不應該是 (a+b+c)* 否則也是被吃光永遠對不完 pattern.@@ 3. (a+b+c+(a|b|c)*) | (a+c+b+(a|b|c)*) | (b+a+c+(a|b|c)*) | (b+c+a+(a|b|c)*) | (c+b+a+(a|b|c)*) | (c+b+a+(a|b|c)*) 這個 abac 就直接爆炸了. 上面的解答要照這樣的格式將會寫成... (a+b(a|b)*c(a|b|c)*) | (a+c(a|c)*b(a|b|c)*) | (b+a(a|b)*c(a|b|c)*) | (b+c(b|c)*a(a|b|c)*) | (c+a(a|c)*b(a|b|c)*) | (c+b(b|c)*a(a|b|c)*) -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.112.30.49 ※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1492304689.A.17D.html ※ 編輯: soulgem (140.112.30.49), 04/16/2017 09:11:25

→

eatmycock

04/16 09:12, , 1^F

04/16 09:12, 1^F

→

soulgem

04/16 09:13, , 2^F

04/16 09:13, 2^F

推

Dark74

04/16 09:23, , 3^F

04/16 09:23, 3^F