3
$\begingroup$

I have a question relating to regular expressions that I'm a bit confused about, If someone can help me out, that would be very much appreciated.

Suppose there exists regular expressions R, S and T.

Then is R*R* R*?

I know the way to prove this is by showing that L(R*) is a subset of L(R*R*) and vice versa, but I have no idea how to do that.. Just started learning about regular languages so I'm a bit confused. Can I please get any direction on how to do this?

$\endgroup$
  • $\begingroup$ The languages denoted by RS and RT aren't the same. 101 is in RS but not in RT. You're on the right track, though. Welcome to the site! $\endgroup$ – Rick Decker Dec 3 '19 at 22:19
2
$\begingroup$

Start with $$ R^*R^* = \left(\bigcup_{i=0}^\infty R^i\right) \left(\bigcup_{j=0}^\infty R^j\right) = \bigcup_{i=0}^\infty \bigcup_{j=0}^\infty R^i R^j = \bigcup_{i=0}^\infty \bigcup_{j=0}^\infty R^{i+j}. $$ As $i,j$ go over all pairs of non-negative integers, $i+j$ goes over all non-negative integers, hence $$ R^*R^* = \bigcup_{i=0}^\infty \bigcup_{j=0}^\infty R^{i+j} = \bigcup_{k=0}^\infty R^k = R^*. $$

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.