Show that if K is regular and M any language, then L is regular

[mathmari]

Hey!

Let $L=\{k |km \in K \text{ for some } m \in M\}$.

How can we show that if $K$ is regular and $M$ is any language, then $L$ is regular?? (Wondering)

 

[Evgeny.Makarov]

This is a nice problem. Take a DFA $(Q,\Sigma,\delta,q_0,F)$ that accept $K$ and make $q\in Q$ accepting iff $\delta(q,m)\in F$ for some $m\in M$. Here $\delta(q,m)$ is the extension of the transition function to strings.

 

[mathmari]

This is a nice problem. Take a DFA $(Q,\Sigma,\delta,q_0,F)$ that accept $K$ and make $q\in Q$ accepting iff $\delta(q,m)\in F$ for some $m\in M$. Here $\delta(q,m)$ is the extension of the transition function to strings.

So, is the transition function of $L$ the same as the transition function of $K$ ? If it stands that $\delta(q,m)\in F$ for some $m \in M$, then we make $q$ an accepting state. So the difference of the description of the two DFA's is the set of final states. Have I understood it correctly?

 

[Evgeny.Makarov]

Yes, you understood it correctly.

 

[mathmari]

Yes, you understood it correctly.

Great! Thank you very much! (Smile)