正則語言的定義

Question

我試過了，並且燒傷了我的大腦，以理解Discrete Mathematics and its Applications(Rosen)中定期語言的定義，但沒有達到理解爲什麼定義與本書相同的目的。在頁（789），我改寫定義：3語法被定義爲

類型：

w1 --> w2 

其中，W1是一個非末端，和w2是以下形式：

w2 = aB 
w2 = a 

式中B爲一非末端，並且a是一個終端。一個特殊情況是，當W1是起點標誌和W2是拉姆達（空字符串）：

w1 = S 
S --> lambda 

兩個問題，我無法找到答案。首先，爲什麼不能w2的形式是Ba。二，爲什麼lambda只允許用於起始符號只有。該書指出，常規語言與Finite State Automaton等價，我們可以很容易地看到我們可以爲這兩種情況構建FSA。我查看了其他資源，這些資源中不存在這些限制。

Answer 1

首先，爲什麼w2不能是Ba的形式。

採取以下語法被W作爲起始符號：

W -> lambda 
W -> aX 
X -> Wb 

它產生一個{Ñ b ^Ñ：n個自然}這是不是一個正則語言。所以這個限制是很重要的，如果你只想生成常規的語言。或者，您可以允許w2 = Ba，但禁止種類規則w2 = aB - 這也會給出常規語言。這個語法會建立一個詞「倒退」。

如果您允許這兩種類型的規則，您將獲得一個名爲linear languages的類。

二，爲什麼lambda只允許用於起始符號。

這不是一個必要的限制。

您可以消除所有對非終結符號的lambda使用：取一些規則W - > lambda，刪除它，並用U - > aW和U - > a替換所有規則U - > aW。顯然，你不能消除對終端符號使用lambda（這種語言不會產生空白字）。

因此，在許多地方使用lambda的每種類型3語法都可以「標準化」爲僅將lambda用於起始符號的語法。