通過構建DFA來查找正則語法是否正確？

練習3：查找語言的正則語法L = { | n + m是奇數數字}。顯示你獲得它的方式。

該問題顯示了我獲得答案的方式。所以這裏是我的解釋。

我們構建DFA

從DFA，我們得到了
小號 - > AA | bA
A - > aS | bS |空

因此，正規文法是
G = {V，T，S，P}
其中
V = {S，A}
T = {A，B}
P = {S - > AA | bA，A - > aS | bS |空}

然而，接下來的問題是：

構造一個DFA接受在練習3.簡化構造DFA如果可能的話由語法產生的語言。

所以我認爲繪製DFA並不是對練習3的預期解釋。也許有另一種方法可以在不繪製DFA的情況下獲得常規語言。請告訴我。

謝謝。

來源

2015-11-04 Haha TTpro

您的DFA匹配所有僅包含a和b的奇數長度的字符串。但是你應該解決的語言是奇數長度的字符串，其中包含一系列運行的bs。因此，您的DFA與aba和baa相匹配，但該語言中唯一帶有2 as和b的字符串是aab – rici

先構建一個（正確的）DFA是獲得常規語法的完美方法。重點是在常規語法和DFA之間進行轉換很容易，因爲它們幾乎完全相同的信息編碼。

正如評論中指出的那樣，您的DFA並不正確。你真的應該有這樣的事情：

state s state' 
------ - ------ 
even_a a odd_a 
even_a b odd_b 
odd_a a even_a 
odd_a b even_b 
even_b a dead 
even_b b odd_b 
odd_b a dead 
odd_b b even_b 
dead  a dead 
dead  b dead

將語法從使用方法會給出正確的事情。請注意，「odd_a」和「odd_b」是接受狀態。

來源

2015-11-23 13:41:45 Patrick87

通常派生DFA比推導grammar更困難。另一件事是，通過首先構建語法，您可以生成與此語法匹配的最小DFA。如果從構建DFA開始，則必須導出相應的語法，然後從該語法中派生最小的DFA。

作爲派生DFA的難點的一個示例：您的DFA與語言a^n b^m, n+m odd不匹配。它匹配所有奇數長度的字符串，即使那些whith a和b混合像：ababa。

我試圖以產生相應的語法：

S -> 'a' L2 
    -> 'b' B2 

    L1 -> 'a' L2 
    -> 'b' B2 

    L2 -> 'a' L1 
    -> 'b' B1 

    B1 -> 'b' B2 

    B2 -> \empty 
    -> 'b' B1

S是開始符號。
L1代表奇數序列a然後b。
L2表示偶數序列a然後b。
B1表示b的奇數序列。
B2表示偶數序列b。

這個語法是正確的，適合構建DFA。

來源

2015-11-23 14:24:51 fjardon

通過構建DFA來查找正則語法是否正確？

回答

相關問題