in Theory of Computation
266 views
2 votes
2 votes
Is (a+ab*b)* and (ab*)* same or not?
in Theory of Computation
by
266 views

1 comment

edited by

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

So, both are equivalent.

4
4

3 Answers

4 votes
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
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.

4 Comments

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

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

0
0
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.$
0
0
1 vote
1 vote

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

 

Hence, both are equal.