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, followe开发者_StackOverflow社区d 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.