轉換的正則表達式規則的語法/右線性文法

Question

我想驗證我的基礎上正確，從這個前一個問題的信息，並通過Grijesh的精彩回答這個正則表達式轉換爲右線性文法：Left-Linear and Right-Linear Grammars

這裏是一個問題：「編寫一個生成由正則表達式（（10）+（011 + 1）+）*（0 + 101）*表示的字符串集合的常規（右線性）語法。」

這裏是我建立起來的語法，在底部我最後的一個是：

1: 
S --> 1 

0: 
S --> 0 

10: 
S --> 1A 
A --> 0 

(10)+: 
S --> 1A 
A --> 0 | 0S 

011: 
S --> 0A 
A --> 1B 
B --> 1 

(011 + 1): 
S --> 0A | 1 
A --> 1B 
B --> 1 

(011 + 1)+: 
S --> 0A | 1 | 1S 
A --> 1B 
B --> 1 | 1S 

(10)+ (011 + 1)+: 
S --> 1A 
A --> 0S | 0B 
B --> 0C | 1 | 1B 
C --> 1D 
D --> 1 | 1B 

((10)+ (011 + 1)+)*: 
S --> 1A | ε 
A --> 0S | 0B 
B --> 0C | 1 | 1B 
C --> 1D 
D --> 1 | 1B 

0: 
S --> 0 

101: 
S --> 1A 
A --> 0B 
B --> 1 

(0 + 101): 
S --> 0 | 1A 
A --> 0B 
B --> 1 

(0 + 101)*: 
S --> 0 | 1A | ε 
A --> 0B 
B --> 1 

((10)+ (011 + 1)+)* (0 + 101)*: 
S --> 1A | ε | E 
A --> 0S | 0B 
B --> 0C | 1 | 1B 
C --> 1D 
D --> 1 | 1B | 1E 
E --> 0 | 1F | ε 
F --> 0G | 0E 
G --> 1 | 1E 

誰能幫我驗證這是否是正確的嗎？謝謝一束！ ：d

Answer 1

一切看起來的權利，直到在這裏：

((10)+ (011 + 1)+)*: 
S --> 1A | ε 
A --> 0S | 0B 
B --> 0C | 1 | 1B 
C --> 1D 
D --> 1 | 1B 

您的內部表達式語法是正確的：

(10)+ (011 + 1)+: 
S --> 1A 
A --> 0S | 0B 
B --> 0C | 1 | 1B 
C --> 1D 
D --> 1 | 1B 

注意，唯一的區別在於允許產生的空字符串。 Kleene封閉增加的不僅僅是空串：它允許重複整個模式。可能這可以通過將產品B --> 1S和D --> 1S添加到第一語法來解決，從而允許任意重複量。

相同的錯誤發生在這個對：

(0 + 101): 
S --> 0 | 1A 
A --> 0B 
B --> 1 

(0 + 101)*: 
S --> 0 | 1A | ε 
A --> 0B 
B --> 1 

第二語法應該添加製作S --> 0S和B --> 1S以允許重複的任意量。

其餘的建設，看起來是正確的，並與上述修復一起應該給一個正確的語法。

注：

1. 使用的算法，從正則表達式
2. 產生NFA使用的算法從NFA
3. （可選）產生DFA使用：您可以通過算法通過這樣做一個算法以最小化DFA
4. 使用算法來從DFA

Ť產生規則語法他在計算帳篷裏的長杆是第2步;如果您能夠完全確定自動機，以消除epsilon/lambda轉換，則此步驟甚至不是真正必要的。之所以足夠的原因是，將DFA轉換爲常規語法的過程將狀態變爲非終結符號，並將f(q, s) = q'轉換映射到生產q := sq'，如果q'接受q := s也映射轉換。只要NFA沒有空轉換，您就可以繼續並使用它。