Cheap and Secure Web Hosting Provider : See Now

[Answers] What's the difference between $a^*+b^*$ and $(a+b)^*$?

, , No Comments
Problem Detail: 

What's the difference between the regular expressions $a^*+b^*$ and $(a+b)^*$. Do both of these generate the same language? I was told in a lecture that $(a+b)^*$ will generate string concatenation of $a$ and $b$. How could this be possible?

Asked By : bhanua1

Answered By : achnichtsowichtig

  1. $a^*+b^*$ generates words that either consist of any amount of $a$s or any amount of $b$s, like: $a$, $aaaaa$, $bbbb$
  2. $(a+b)^*$ generates secquences of either $a$ or $b$, for example: $abab$, $aabb$, $bbaa$,...

So, the main difference is, that in 1 you either get strings only containing as or only containing bs. Regex 2 produces a language where you have no order of characters and can put both in.

So, both don't produce the same language, but 1 is a subset of 2.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/45286

3.2K people like this

 Download Related Notes/Documents

0 comments:

Post a Comment

Let us know your responses and feedback