Regular language restricted to smaller alphabet is regular

576 Views Asked by At

Let $L$ be a regular language on some alphabet $\Sigma$, and let $\Sigma_1 \subset \Sigma$ be a smaller alphabet. Consider $L_1$ the subset of $L$ whose elements are made up only of symbols from $\Sigma_1$, that is $$ L_1 = L \cap \Sigma_1^* $$ Show that $L_1$ is also regular.

By intuition, I would say that if L1 is a subset of L and that L is regular, then L1 is also regular, because L1 has less states than L2 and therefore there must be an automata for L1 too. However, I am pretty sure it's not a sufficient proof. Why is that? And how do I develop the intuition to be able to see straight away what I need to do. I can't find any example on the Internet and this is some complex stuff we have here.