Regular expression

Question

Is (a+ab*b)* and (ab*)* same or not?

Comments

(a + ab*b)*= (a(epsilon + b*b))* = (a(epsilon + b^+))* = (ab*)*

So, both are equivalent.

Answer 1

As we know that $(r)^*=\epsilon,r,rr,rrr,rrrr...\infty$,$0$ or more occurrence of r.

For eg: $(ab)^*$ can generate $0$ or more occurrence of string $ab$.

This regular expression can generate following strings:$(\epsilon,ab,abab,ababab....)$

In the same way $(ab^*)^*=(\epsilon,ab^*,ab^*ab^*,ab^*ab^*ab^*…...)$,which can also be written as: 

$(ab^*)^*=(\epsilon,a,ab,abb…,aa,aba,aab,abba,abab,ababb….)\equiv(\epsilon+a(a+b)^*)$

Now another regular expression $(a+ab^*b)^*$ can be written as:

$(a+ab^*b)^*=(a(\epsilon+b^*b)^*)\rightarrow(a(\epsilon+b^+))^*\rightarrow(a(\epsilon+b,bb,bbb,bbbb….))^*\rightarrow (a,ab,abb,abbb,abbbb….)^*\equiv(ab^*)^*$

$\therefore (ab^*)^*\equiv (a+ab^*b)^*$ both the regular expression generate the same sets of strings.

 

Answer 2

S1: (a+ab*b)*

S2 = (ab*)* = (a+ab*)* = (a+ab*b)*

Any strings with any number of a’s consecutively in S2 will get covered by the first part of S1. In any case, when there is atleast one occurence of b, the second part of S1 will cover it.

Hence, both are equal.

Comments

@DebSujit there is a typo in S2

S2 = ($a$$b^{*}$) = ( a . ( $b^{0}$ + $ b^{+}$) )  =  ( $a^{}$ + a$ b^{+}$) = ( $a^{}$ + a$ b^{*}$$b^{}$)

 

 

---

@DebSujit how $b^{*}$ can be equal to $b^{*}b$?  $b^{*}b$ means $b^{+}$.

---

@samarpita a+ab* ensures that there must be one a before any b, which can be written in condensed form as (ab*),

which can be further written as (ab*+abb*).

Now, ab* can be re-written as only a as for any occurrence of b it will fall under abb*. 

a+ab* = ab* = ab* + abb* = a + abb* = a+ab*b 

---

Saying “Regular expressions are equal” is technically incorrect. “Equal” should be replaced with “Equivalent” i.e. “Regular expressions are equivalent”.

“Equal” and “Equivalent” have different meaning in mathematics.

“Equivalent” is associated with some equivalence relation.

---

@ankitgupta.1729 exactly. Equal implies equivalent but equivalent doesn’t mean equal.

---

Yes. Suppose, both regular expressions are equivalent and associated with a regular language $R.$ then the equivalence relation here would be:

$$x \equiv_R y \overset{\textit{def}}\Leftrightarrow \forall z \in \Sigma^* (xz \in R \Leftrightarrow yz \in R)$$

It says two strings are equivalent under equivalence relation $\equiv_R$ whenever you append the same string $z$ in both of them, the resulting two strings are either both in $R$ or both not in $R.$

For example, here, from first regular expression, take $x = a$ and from second regular expression, take, $y= ab$ and when you pick $z = bab$ then $xz = abab$ and $yz = abbab,$ here, both $xz$ and $yz$ are in $R.$

Answer 3

DFA for (a+ab*b)* and (ab*)*

 

Hence, both are equal.