patternMinor
Prove the equivalence of regular expressions
Viewed 0 times
theregularexpressionsproveequivalence
Problem
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(RR*) 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?
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(RR*) 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?
Solution
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^*.
$$
$$
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^*.
$$
Context
StackExchange Computer Science Q#118028, answer score: 3
Revisions (0)
No revisions yet.