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

**So, both are equivalent.**

Dark Mode

nbhatt
asked
in Theory of Computation
Sep 15

269 views
4 votes

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.

2 votes

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.

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.

1

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

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

0