Given a language $L_1$ over the $\Sigma$ alphabet, is the following statement correct?

82 Views Asked by At

Given a language $L_1$ over $\Sigma$ alphabet, is
$L_1L_1^*L_1=L_1^*L_1^2\cap L_1^2\Sigma^*$
Correct?
I started by simplifing the expression to : $L_1^*= L_1^*\cap L_1^2\Sigma^*$
Now, my problem was understanding the right side. I think the statement is correct, because $L_1^*\subseteq \Sigma^*$, so $L_1^*\cap L_1^2\Sigma^*=L_1^*\cap L_1^*=L_1^*$
Is that right?

1

There are 1 best solutions below

0
On

It can be done as a single calculation rather than by showing that each side is a subset of the other:

$$\begin{align*} L_1^*L_1^2\cap L_1^2\Sigma^*&=\left(\bigcup_{n\ge 0}L_1^nL_1^2\right)\cap\bigcup_{n\ge 0}L_1^2\Sigma^n\\ &=\left(\bigcup_{n\ge 2}L_1^n\right)\cap\bigcup_{n\ge 0}L_1^2\Sigma^n\\ &=\left(\bigcup_{n\ge 0}L_1^2L_1^n\right)\cap\bigcup_{n\ge 0} L_1^2\Sigma^n\\ &=\bigcup_{n\ge 0}\bigcup_{m\ge 0}(L_1^2L_1^n\cap L_1^2\Sigma^m)\\ &=L_1^2\bigcup_{n\ge 0}\bigcup_{m\ge 0}(L_1^n\cap\Sigma^m)\\ &=L_1^2\bigcup_{n\ge 0}L_1^n\\ &=\bigcup_{n\ge 2}L_1^n\\ &=L_1\left(\bigcup_{n\ge 0}L_1\right)L_1\\ &=L_1L_1^*L_1 \end{align*}$$