通过构建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来查找正则语法是否正确？

回答

相关问题