1樓：
理論上說，正規表示式就是符合Chomsky層級中type3文法的字串，那麼肯定是不完備的，至少連(1^n)(2^n)這樣的字串都無法描述。
但是實際的正規表示式引擎實現中，有時為了增強匹配字串的能力，會讓該引擎的語法達到type2乃至type0。比如Perl6的正規表示式可以完全匹配CFG（type2），.NET中的正規表示式也接近CFG，而sed語法則是圖靈完備的（type0）。
這時按照習慣也叫「正規表示式」，但是本質上已經超越了理論的正規表示式，有時也叫「擴充套件的正規表示式」。
2樓：metalmoon
不是的，正規表示式的能力和有窮狀態機fsm等價，夠不著下推自動機，下推自動機夠不著圖靈機，有窮狀態且沒有額外的儲存限制了fsm的能力。
3樓：Htedsv
說個容易理解的說法：圖靈機模型最壞的情況下是可能執行無限時間，無限空間。
DFA最壞情況也只要O(1)的空間（只要記錄當前指標位於哪個狀態），O(n)的時間（遍歷整個要判別的字串），即它只能處理這個複雜度範圍的問題，所以肯定處理問題的範圍肯定更小。
4樓：不會寫程式碼的喵
圖靈完備是對計算模型說的吧，正規表示式本身不是計算模型。題主想說的是DFA（NFA、帶空串轉移的NFA）？不是圖靈完備。
你是如何學會正規表示式的？
一絲混亂 大部分知識和技能的都符合二八定律 20 知識點的使用頻率是80 80 知識點的使用頻率是20 但是這些東西的教程或者說明是一股腦兒全部給你的，並沒有著重標出哪些是重點，哪些用的頻率不那麼高。正則就是一個非常典型的例子，我覺得正則說是9.5 0.5都不為過。我使用過程中，用到最多的是i g ...
正規表示式匹配失敗是如何回溯的？
Belleve 在 PEG 文法裡 用後者展開即可得到以下的模式 Matcher a 是一個函式，接入三個引數 匹配狀態 s，成功續體 success 和失敗續體 failure 在任意狀態 s 下匹配空模式 總是成功，故可以直接用封裝的 success s function Directly su...
關於cool語言和正規表示式的問題？
non escaped newline character的意思就是非轉義的換行符。對於詞法分析器來說，一個新行的開始不是我們平常感覺的一行的開頭，而是上一行的終結符號 看不到的 n或者 n r 上面的意思是說，字串不能跨行，如果想跨行寫字串，必須使用 來指明說要換行了。轉義字元 你看到的字元不是你...
正規表示式檢驗質數的原理是什麼？
Pirate 遂仔細想了一下題主這個正則式 1 似乎有些問題，首先這個正則式可以分為兩個部分 第一個部分 第二個部分 1 匹配頭，匹配尾，單個字元，1至n多個，前面的字元是否出現，1引用前面的匹配 先說第一個部分，意思是匹配任意單一字元或者無字元。似乎在這個情況下，0,1,2,3,4,5.都是可以匹...
正則化和正規表示式的共同點是什麼？
閒雲野鶴 沒有關係，正則化是為了防止過擬合在經驗風險中加入罰函式的過程。正規表示式是幫助我們檢查某個序列是否符合特定模式。二者無關，應該是翻譯問題。 鉛筆 雷鋒和雷鋒塔。這個真的太切題了。正則化是機器學習裡面避免過擬合而採用的一種使擬合誤差儘量小，模型也儘量簡單的技術。當然有時候也有其他副產品，比如...