(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. so what's is the reject state of this RE ?
Just think about the strings that is not accepted by (ab+ba)*.
A:
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.
paxdiablo
2010-07-21 04:26:43
'+' is often used to denote alternation, so an equivalent expression would be (ab|ba)* (going by the given expression rather than the English description).
Jim Lewis
2010-07-21 05:32:00
+1
A:
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.
Jim Lewis
2010-07-21 05:24:45