(ab+ba)*
接受所有零个或多个“a”,后跟零个或多个“b”,以及零个或多个“b”,后跟零个或多个“a”。这个 RE 的拒绝状态是什么?
想想那些不被(ab+ba)*
.
(ab+ba)*
接受所有零个或多个“a”,后跟零个或多个“b”,以及零个或多个“b”,后跟零个或多个“a”。这个 RE 的拒绝状态是什么?
想想那些不被(ab+ba)*
.
关于术语的几点说明: 正则表达式没有状态——拒绝、接受或其他。(纯)正则表达式描述正则语言。常规语言也没有状态;只是作为语言元素或非元素的字符串。可以讨论一种语言的补语:同一字母表中不是该语言元素的字符串集。正则语言的补语恰好也是正则语言。每一种常规语言都可以用一个有限自动机来描述,而正是这个自动机具有拒绝或接受状态。
给出正则表达式并询问其“拒绝状态”是不正确的——可能有许多描述相同正则语言的自动机,并且必须指定正在考虑哪些可能性。
我假设您要求的字符串描述不是由表达式 (ab + ba)* 指定的语言,甚至可能是描述该语言相对于 (a+b) 的补码的正则表达式*。
您可能会尝试的一种方法是找到一个识别该语言的 DFA,然后将所有接受状态更改为拒绝状态,反之亦然。生成的 DFA 可以识别原始语言的补码,并且(通过一些巧妙的方法——留给读者作为练习)可以将其转换回正则表达式。
好吧,考虑一下(这很重要——这是你的功课,你需要理解)。
根据您的描述(顺便说一句,您的实际 RE 采用一种非常奇怪的形式,与我使用的任何 RE 格式完全不同 - 在更常规的 RE 语言中,它会是a*b*|b*a*
),除非您在开始时有隐式锚点,否则没有拒绝条件和字符串的结尾(在这种情况下,aba
将被拒绝)。
您所有的约束都是“零或更多”这一事实意味着任何字符串都会通过。