Demostrar que un lenguaje de construir a partir de dos idiomas es regular así

Question

Deje $L, M \subseteq \Sigma^*$ ser regulares de idiomas. Tengo que demostrar que $$N = \{x \in \Sigma^* \; | \; \exists y \in L : xy \in M\}$ $ , así como un lenguaje regular.

Mi favorecido enfoque es encontrar una máquina de estados finitos que reconoce que el idioma. Yo pensaba acerca de la FSM, que reconoce a M e $\lambda$-de las transiciones a la FSM de $L$, pero esto no me ayuda en esto. No sé cómo integrar el reconocimiento de $L$ a cada paso de $M$ y estoy atascado.

Podría usted por favor me ayude con eso?

Gracias de antemano!

Answer 1

Tome una máquina de estado para $M$. Dado un estado de $\alpha$ en esa máquina, podemos decir que el $\alpha$ $L$- completo si, por alguna cadena de $y\in L$, a partir de $\alpha$, los rendimientos de un partido exitoso.

Ahora, crear una nueva máquina que utiliza la misma máquina de estado como $M$, pero que el registro de un "match" sólo en el $L$-completar los nodos.

Usted realmente no necesita saber cómo averiguar qué nodos se $L$-completa, usted sabe que son un subconjunto del estado de los nodos.

Ésta no es una solución constructiva, en la que no te muestran cómo determinar el $L$-completa nodos, de modo que usted no puede utilizar este argumento para hacer que la máquina para $N$ fuera de conocidos máquinas para$L$$M$.

De hecho, esta prueba no parecen necesitar $L$ a ser regular.