正則語言的定義

我試過了，並且燒傷了我的大腦，以理解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。我查看了其他資源，這些資源中不存在這些限制。

2010-05-21 AraK

你檢查過這本書是否有勘誤？ – 2010-05-21 22:15:40

@David M不，我沒有那樣做，但現在我會做。有趣的是，在頁面（795）練習＃19（i，j）正是按照這個定義來解決的。 – AraK 2010-05-21 22:19:11

我剛剛檢查了第六版的勘誤表。並沒有發現任何東西：http：//highered.mcgraw-hill.com/sites/dl/free/0072880082/299357/Rosen_errata.pdf – AraK 2010-05-21 22:23:15

首先，爲什麼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用於起始符號的語法。

2010-05-21 22:42:22 sdcvvc

很好的答案。非常感謝：） – AraK 2010-05-21 23:01:57

回答