设 {a b} 为字母集,写出正则表达式:
1)所有a和b的数量均为奇数的单词的语言;
2) 所有长度为奇数且包含子串 ab 的单词的语言。
另外,如果可能的话,请帮我找到两种不同的表达方式,以帮助加强我对如何解决此类问题的理解。
最佳答案
对于第一个,您可以构建一个简单的 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。这是该表...
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, ...} 看起来不错我!
每个步骤的减少规则可以形式化,或者您可以应用仔细的推理来确保您得到正确的结果。检查克莱恩定理的证明以进行仔分割析。另外,Martin 的《形式语言简介》或其他书籍有使用此算法的很好的示例。
关于regex - 查找其他描述的语言的正则表达式,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/7626800/