正则表达式：`(ab+ba)*` 不接受的字符串
(ab+ba)* 接受零个或多个“a”后跟零个或多个“b”，以及零个或多个“b”后跟零个或多个“a” s。该 RE 的拒绝状态是什么？
想想 (ab+ba)* 不接受的字符串。
(ab+ba)* accepts all zero or more "a"s followed by zero or more "b"s, and also zero or more "b"s, followed by zero or more "a"s. What is the reject state of this RE?
Just think about the strings that are not accepted by (ab+ba)*.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
好吧，想一想（这很重要 - 这是你的作业，你需要理解）。
根据您的描述（顺便说一句，您的实际 RE 的形式非常奇怪，与我使用过的任何 RE 格式都不相同 - 在更常规的 RE 语言中，它将是
a*b*|b*a*)，除非在字符串的开头和结尾有隐式锚点，否则不存在拒绝条件（在这种情况下，aba将被拒绝）。事实上，所有约束都是“零个或多个”，这意味着任何字符串都会通过。
Well, think about it (and this is important - it's your homework and you need to understand).
Based on your description (your actual RE is in a very strange form BTW, nothing like any RE format I've used - in more regular RE language, it would be
a*b*|b*a*), there is no reject condition unless you have implicit anchors at the start and end of the string (in that case,abawould be rejected).The fact that all of your constraints are "zero or more" means that any string will pass.
关于术语的一些注意事项： 正则表达式没有状态——拒绝、接受或其他。 （纯）正则表达式描述正则语言。常规语言也没有状态；只是作为元素的字符串或
非语言元素。人们可以讨论一种语言的补集：集合
同一字母表上不是语言元素的字符串。碰巧，正则语言的补集也是正则语言。每种正则语言都可以用有限自动机来描述，并且正是该自动机具有拒绝或接受状态。
给出正则表达式并询问其“拒绝状态”是不正确的——
可能有许多自动机描述同一种正则语言，并且一个人会
指定正在考虑哪些可能性。
我假设您要求提供一些不属于该语言的字符串的描述
由表达式 (ab + ba)* 指定，甚至可能是描述
该语言关于 (a+b)* 的补集。
您可以尝试的一种方法是找到可识别该语言的 DFA，然后
将所有接受状态更改为拒绝状态，反之亦然。由此产生的
DFA 识别原始语言的补语，并且（有点聪明——
留给读者作为练习）这可以转换回常规
表达。
A few notes about terminology: Regular expressions do not have states -- rejecting, accepting, or otherwise. (Pure) regular expressions describe regular languages. Regular languages do not have states either; just strings that are elements or
not-elements of the language. One can discuss the complement of a language: the set
of strings over the same alphabet that are not elements of the language. It so happens that the complement of a regular language is also a regular language. Every regular language can be described by a finite automaton, and it is this automaton that has rejecting or accepting states.
It is incorrect to give a regular expression, and ask for its "rejecting states" --
there may be many automata that describe the same regular language, and one would have
to specify which of those possibilities is being considered.
I'll assume you're asking for some description of strings that are not in the language
specified by your expression (ab + ba)*, perhaps even a regular expression that describes the
complement of this language with respect to (a+b)*.
One approach you might try is to find a DFA that recognizes that language, then
change all accepting states to rejecting states and vice-versa. The resulting
DFA recognizes the complement of the original language, and (with some cleverness --
left as an exercise for the reader) this can be converted back to a regular
expression.