2
$\begingroup$

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*?

$\endgroup$
  • $\begingroup$ I think you'll need to edit the question, as I can't tell what you are asking. 1. (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
  • $\begingroup$ 3. Please use typesetting to reduce ambiguity. Does (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
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ But a* means that there can be even 0 a's. en.wikipedia.org/wiki/Regular_expression#Basic_concepts $\endgroup$ – Adwait Kumar Sep 4 '15 at 4:10
  • $\begingroup$ @AdwaitKumar the issue is not in 0 a's between bb, but your regular expression a*(bab)*not permit aa between 2 bb's . expand it a bit you can get a*(bab)(ba*b)..., clearly it forces no a's between 2nd and 3rd b's, etc. $\endgroup$ – Terence Hang Sep 4 '15 at 6:12
  • $\begingroup$ In fact $(a+ba^*b)^* $ does correctly represent an even number of $b$'s. The expression has a repeated alternative between a single $a$ and a sequence of two $b$'s with an arbitrary numbers of $a$'s in between. The star allows zero iterations. Also $a^*(ba^*b)^* $ is indeed wrong, but it will match $a$'s between $b$'s. The reason it is wrong is that we cannot end with the letter $a$ unless we only have $a$'s. $\endgroup$ – Hendrik Jan Sep 5 '15 at 22:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.