Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
I came across a question to create a regular expression to check whether there are even number of b's in a string of language {a,b}. The expression I came up with is (a+ba*b)*. However I found the solution online to be a*(ba*ba*). Is there any difference? If any where?
Also I know that (a+b)* is equivalent to (a*b*)*. So my solution comes out to be (a*(ba*b))*. So why that extra a*?
Your regular expression (a+ba*b)* won't match the string a which contains zero b's, an even number. It also won't match the strings bb or bbbb, because the expression requires one or more a's before any occurring b's and requires at least one a between any two pairs of b's.
The regular expression a*(ba*ba*)* is the correct solution. It allows any number of leading a's and then demands that there if there are b's present there be at least two b's among the remaining a's. Thereafter b's are matched in groups of two among the a's and matching will fail if a b occurs outside such a pair.
The regular expression a*(ba*b)* is wrong because it won't match strings with a's between pairs of b's, such as the string bbaabb.
(a+b)*is not equivalent to(a*b*). Please double-check all your statements. Proof-read the formatted output, and consider using Markdown to typeset your notation more clearly. 2. What have you tried? Have you tried to look for a string that is accepted by your expression but not by the other one, or vice versa? Have you taken a look at closure properties, to see how to compute the set difference between two regexps? (continued) $\endgroup$ – D.W.♦ Sep 3 '15 at 21:33(a+ba*b)*mean(a+(ba*b))*or((a+b)a*b)*? 4. I can't tell what "check whether for even number of b's in a language of {a,b}" means. Can you please edit to rewrite that? Thank you! $\endgroup$ – D.W.♦ Sep 3 '15 at 21:33