I have a quick question to ask. So I am trying to come up with a regular epxression which represent a language over {a,b} that contains at least one 'b' in it.
I came up with this:
$$(a| b)^*b(a| b)^*$$
My friend come up with this
$$a^*b(a| b)^*$$
I think these two are equivalent; however, I couldn't simply the first one to get the second one. SO my question is, is it true that two equivalent regular expression would have the different form?
Or correct me if any part is wrong. Thanks ahead!!
To show that these two expressions are equivalent, you must show how to translate from one to the other. Start with a string in $(a\cup b)^*b(a\cup b)^*$. There are two cases: Either the substring consisting of the first $(a\cup b)^*$ contains a $b$, or it doesn't. If the substring doesn't contain a $b$, then the string you started with is already in $a^*b(a\cup b)^*$. Otherwise, it contains a first $b$. So this substring can be written as an element of $a^*b(a\cup b)^*b(a\cup b)^*$. Now everything after the first $b$ is just a string in $a$ and $b$, so we can rewrite this expression as an element of the language $a^*b(a\cup b)^*$ as desired.
This shows that every string in $(a\cup b)^*b(a\cup b)^*$ is also in $a^*b(a\cup b)^*$. You can use a similar argument to show the reverse inclusion.