regex - 查找其他描述的语言的正则表达式

Question

令 {a b} 为字母集，写一个正则表达式:

1)a和b的个数都是奇数的所有单词的语言；

2) 所有长度为奇数且包含子串 ab 的单词的语言。

另外，如果可能的话，请帮我找到两个不同的表达方式，以帮助我加深对如何解决这些问题的理解。

Answer 1

对于第一个，您可以构建一个简单的 4 状态 DFA 来识别语言。然后，您可以使用可从 Kleene 定理(他说 FA 识别的所有语言均由 RE 生成的部分)恢复的算法来获得有效的 RE……或者只是从图中推理出来。

对于第二个，您知道 (ab) 是 RE 的一部分；现在，您需要考虑所有可以向其添加奇数个字符(正面或背面)的独特方式，并将所有这些可能性与 + 联系起来，以获得简单、正确的 RE。

我认为没有人特别喜欢只给你答案的想法。

编辑:

所以现在已经过了一段时间，我将完成第一个的答案，向感兴趣的读者展示如何做到这一点。

我们的第一个 FA 是这样的:

   Q s f(Q, s)
  -- - -------
  EE a     OE
  EE b     EO
  OE a     EE
  OE b     OO
  EO a     OO
  EO b     EE
  OO a     EO
  OO b     OE

我们将从中删除状态并用正则表达式替换 s 以覆盖该状态。我们从一个简单的开始……让我们摆脱 OE。这是 table ...

   Q                  regex f(Q, s)
  -- ---------------------- -------
  EE                     aa      EE
  EE                     ab      OO
  EE                      b      EO
  EO                      a      OO
  EO                      b      EE
  OO                      a      EO
  OO                     ba      EE
  OO                     bb      OO

在继续之前说服自己这是正确的。接下来，我们摆脱 EO:

   Q                  regex f(Q, s)
  -- ---------------------- -------
  EE                  aa+bb      EE
  EE                  ab+ba      OO
  OO                  ab+ba      EE
  OO                  aa+bb      OO

为了使下一步更简单，我们引入了一个新的起始集 X 和一个新的接受状态 Y； OO 不再接受。我们消除了对 OO 的需要:

   Q                        regex f(Q, s)
  -- ---------------------------- -------
   X                        empty      EE
  EE aa+bb+(ab+ba)(aa+bb)*(ab+ba)      EE
  EE              (ab+ba)(aa+bb)*       Y

因此，最终的正则表达式是

  (aa+bb+(ab+ba)(aa+bb)*(ab+ba))*(ab+ba)(aa+bb)*

我们可以开始尝试列出生成的最小字符串，就像基本的完整性检查:{ab, ba, aaab, aaba, bbab, bbba, abaa, abbb, baaa, babb, ...} 看起来不错!

每一步减少的规则可以被形式化，或者你可以应用仔细的推理来确保你得到正确的东西。检查 Kleene 定理的证明以进行仔分割析。此外，Martin's Introduction to Formal Languages 或其他东西有使用这种算法的很好的例子。