English 中文(简体)
Regular expressions: strings that are not accepted by `(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)*.

问题回答

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, aba would be rejected).

The fact that all of your constraints are "zero or more" means that any string will pass.

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.





相关问题
Uncommon regular expressions [closed]

Recently I discovered two amazing regular expression features: ?: and ?!. I was curious of other neat regex features. So maybe you would like to share some tricky regular expressions.

regex to trap img tag, both versions

I need to remove image tags from text, so both versions of the tag: <img src="" ... ></img> <img src="" ... />

C++, Boost regex, replace value function of matched value?

Specifically, I have an array of strings called val, and want to replace all instances of "%{n}%" in the input with val[n]. More generally, I want the replace value to be a function of the match ...

PowerShell -match operator and multiple groups

I have the following log entry that I am processing in PowerShell I m trying to extract all the activity names and durations using the -match operator but I am only getting one match group back. I m ...

Is it possible to negate a regular expression search?

I m building a lexical analysis engine in c#. For the most part it is done and works quite well. One of the features of my lexer is that it allows any user to input their own regular expressions. This ...

regex for four-digit numbers (or "default")

I need a regex for four-digit numbers separated by comma ("default" can also be a value). Examples: 6755 3452,8767,9865,8766,3454 7678,9876 1234,9867,6876,9865 default Note: "default" ...

热门标签