regex - 正则表达式：`(ab+ba)*` 不接受的字符串

Question

(ab+ba)*接受所有零个或多个“a”，后跟零个或多个“b”，以及零个或多个“b”，后跟零个或多个“a”。这个 RE 的拒绝状态是什么？

想想那些不被(ab+ba)*.

Answer 1

关于术语的几点说明： 正则表达式没有状态——拒绝、接受或其他。（纯）正则表达式描述正则语言。常规语言也没有状态；只是作为语言元素或非元素的字符串。可以讨论一种语言的补语：同一字母表中不是该语言元素的字符串集。正则语言的补语恰好也是正则语言。每一种常规语言都可以用一个有限自动机来描述，而正是这个自动机具有拒绝或接受状态。

给出正则表达式并询问其“拒绝状态”是不正确的——可能有许多描述相同正则语言的自动机，并且必须指定正在考虑哪些可能性。

我假设您要求的字符串描述不是由表达式 (ab + ba)* 指定的语言，甚至可能是描述该语言相对于 (a+b) 的补码的正则表达式*。

您可能会尝试的一种方法是找到一个识别该语言的 DFA，然后将所有接受状态更改为拒绝状态，反之亦然。生成的 DFA 可以识别原始语言的补码，并且（通过一些巧妙的方法——留给读者作为练习）可以将其转换回正则表达式。

Answer 2

好吧，考虑一下（这很重要——这是你的功课，你需要理解）。

根据您的描述（顺便说一句，您的实际 RE 采用一种非常奇怪的形式，与我使用的任何 RE 格式完全不同 - 在更常规的 RE 语言中，它会是a*b*|b*a*），除非您在开始时有隐式锚点，否则没有拒绝条件和字符串的结尾（在这种情况下，aba将被拒绝）。

您所有的约束都是“零或更多”这一事实意味着任何字符串都会通过。