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

### 1 comment

edited

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

So, both are equivalent.

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.

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.
by

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.$

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

Hence, both are equal.

1
192 views