什麼是規律？

這是一個計算機科學問題，而不是一個編程問題，但我認爲這是所有相關網站中最好的地方。什麼是規律？

當我發現正則表達式，擡頭我以爲，「規律性」的這個屬性指的是表達的語言具有自定義結構模式的事實項。然而，在閱讀關於這個主題和背後的理論時，我瞭解到有些語言是不規則的，但從定義的方式來看，很明顯一種模式可以與它們匹配。一種這樣的語言是（a^n）（b^n）。顯然這是一種模式，但這不是一種常規語言。所以現在我還想知道那些使它們正常的常規語言是什麼，而這種語言不是？

來源

2010-01-09 EpsilonVector

纖維填充飲食的產品？ –

+10

你會知道，米奇*小麥*。 – 2010-01-09 02:13:37

名稱的詞源來自Kleene的20世紀50年代工作描述常規集使用他爲此目的創建的數學符號。見this。

來源

2010-01-09 01:56:23 wallyk

@Barry Kelly：感謝您的錯字修復。我本來打算回去檢查一下這個詞。 – wallyk

regular這個詞在regular expression指的是數學概念，而不是英語的概念。就像數學中的prime這個詞如何與素數牛肉沒什麼關係。

它是由CS（這是數學的一個分支）繼承是指一個更具體的概念：http://en.wikipedia.org/wiki/Regular_language

來源

2010-01-09 02:03:01 slebetman

正則表達式是不是真的有規律，名稱是詞源。

來源

2010-01-09 02:03:58

正則表達式是正則表達式，但正則表達式不是。具體來說，正則表達式是Perl稱之爲類似regexp的語法，以區別於傳統的正則表達式。還有一些語言仍然實現了真正經常使用的正則表達式：tcl和awk來命名兩個。 – slebetman

也許在regular languages維基百科的文章能比我們可以更好地解釋它。但是，我會給它一個鏡頭。

從理論的角度來看，一個正則語言（組字符串）是可以使用一個finite state automaton來生成一個。用程序員的話來說，這相當於說它可以使用regular expressions生成。因此，所有的有限語言（琴絃組）有規律的，但也有一些無窮的語言，如^ñ b ^ñ（後跟n B的NA的所有字符串的語言），可以不使用被認可FSA或正則表達式。還有更強大的計算設備（如使用Turing Machines建模的現代計算機），其中可以識別那些語言。

正則表達式在字符串搜索編程中被廣泛使用的原因是，它們可以識別大部分對我們程序員很重要的字符串，同時可以通過使用有限元來快速搜索很快狀態自動機。

來源

2010-01-09 02:04:57

錯誤。程序員的正則表達式通常不是**定義常規語言的方式。 RegExps更通用（因爲它們可以識別所有常規語言和許多其他語言）。 –

什麼？給我一個可以被程序員的正則表達式識別但不是理論正則表達式的語言的例子。 –

並非所有的正則表達式都是正則表達式。一些語言實現了真正規則的正則表達式，而不是Perl正則表達式的克隆。 – slebetman

直觀地解釋計算機科學是棘手的。我會試試看，但請記住，其中一些會「足夠接近」，但不是理論上的嚴格。

正則語言是一個可以由一臺機器，是計算相當於一個有限自動機（DFA/NDFA）來決定。有限自動機可以被認爲是純粹在狀態下操作的機器，沒有存儲。所以，你可以看到一個^ň b ^ň不能經常因爲它需要一臺能夠計算A和B的數量（因此必須有無限*存儲容量），以便對它們進行比較。

作爲比較，（abc）ⁿ是正常，因爲重複的次數是不相關的。

對於更嚴格（和相應更密集的視圖）檢查wikipedia article和鏈接的頁面。

_{*這裏無限無關緊要，但爲了完整性，我提到它。把它想成「幸運，總是足夠」的存儲可能會更容易。}

來源

2010-01-09 02:05:59

+1爲「國家，無存儲」評論，我忘了提及。 –

我覺得它最簡單的想法是這樣的：DFA /普通 - >沒有存儲，PDA/CFL - >有限存取的無限存儲，TM - >隨機存取的無限存儲 –

什麼是規律？

回答

相關問題