4

这是我的作业。

练习 3：找出语言 L = { a^nb^m|的正则文法 n + m 是奇数}。展示你获得它的方式。

问题要求显示我获得答案的方式。所以这是我的解释。

我们从 DFA 构造DFA，我们得到S -> aA | bA A -> aS | BS | null因此，正则文法为 G = {V , T , S, P}其中V = {S, A} T = {a, b} P = {S -> aA | bA, A -> aS | BS | 无效的}
DFA











然而，下一个问题是：

构造一个接受由练习 3 中的语法生成的语言的 DFA。如果可能，简化构造的 DFA。

所以我认为绘制DFA并不是练习3的预期解释。也许还有另一种方法可以在不绘制DFA的情况下获得正则语言。请告诉我。

谢谢你。

4

2 回答 2

1

通常推导DFA比推导语法更难。另一件事是，通过首先构建语法，您可以生成与该语法匹配的最小 DFA。如果您从构建 DFA 开始，则必须推导出相应的文法，然后从该文法推导出最小 DFA。

举例说明为什么派生 DFA 更难：您的 DFA 与语言不匹配a^n b^m, n+m odd。它匹配所有奇数长度的字符串，即使是那些 whitha和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 then b的奇数序列。
  • L2表示a then b的偶数序列。
  • B1表示 的奇数序列b。
  • B2表示 的偶数序列b。

这个语法是正则的，适合构建 DFA。

于 2015-11-23T14:24:51.913 回答
0

首先构造一个（正确的）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-23T13:41:45.217 回答