正規文法到我的正則表達式/ DFA

Question

我有以下的正則表達式：（（ABC）+ d）|（？EF * G）

我創建了一個DFA（我希望這是正確的），你可以看到這裏

http://www.informatikerboard.de/board/attachment.php?attachmentid=495&sid=f4a1d32722d755bdacf04614424330d2

的任務是創建一個常規的語法（喬姆斯基層次類型3），我不明白這一點。但是，我創建了一個正規文法，它看起來像這樣：

小號→在

牛逼→早

T→C

牛逼→德尚

小號→等

S→eS

T→ε

Ť→˚F

Ť→FS

Ť→GS

此致 帕特里克

Answer 1

3類型斯基是類收縮的用途的以下規則正規文法的：

X -> aY 
X -> a, 

其中X是任意的非項inal和一個任意的終端。規則A -> eps只有在A不存在於任何右側時才被允許。

建設

我們注意到正則表達式包含兩種可能，要麼（ABC）+ d或EF * G？我們的第一個規則將爲此是S -> aT和S -> eP。這些規則允許我們開始創造兩種可能性中的一種。請注意，非終端必然不同，這是完全不同的相應自動機中的分離路徑。下一步我們將繼續與獨立兩者的正則表達式：

（ABC）+ 我們後跟0個或多個至少一個序列ABC，不難看到大家能夠喜歡這款機型的：

S -> aT 
T -> bU 
U -> cV 
V -> aT # repeat pattern 
V -> d # finish word 

ef * g？在這裏，我們有一個電子後跟零個或更多f的字符和一個可選克，因爲我們已經有了第一個字符（前兩個規則，一個給了我們），我們將繼續這樣的：

S -> eP 
S -> e # from the starting state we can simply add an 'e' and be done with it, 
      # this is an accepted word! 
P -> fP # keep adding f chars to the word 
P -> f # add f and stop, if optional g doesn't occur 
P -> g # stop and add a 'g' 

結論

把它們放在一起，它們將形成語言的語法。我試圖寫下思路，以便你能理解它。

作爲練習，嘗試此正則表達式：（A + B *）BC（A | B | C）*