¿Cómo probar que los idiomas regulares están cerrados bajo el cociente izquierdo?

$L$ es un lenguaje regular sobre el alfabeto . El cociente izquierdo de respecto a es el lenguaje $\Sigma = \{a,b\}$ $L$ $w \in \Sigma^*$

w^{- 1} L := {v ∣ w v \in L}

$w^{-1} L := \{v \mid wv \in L\}$

¿Cómo puedo probar que $w^{-1}L$ es regular?

formal-languages regular-languages closure-properties corium
fuente

Respuestas:

Supongamos que $M$ es una máquina de estado finito determinista aceptar $L$ . Introduce la palabra $w$ en $M$ , que te llevará a algún estado $q$ . Construya una nueva máquina $M'$ que sea igual a $M$ pero que tenga el estado de inicio $q$ . REIVINDICACIONES que $M'$ acepta $w^{-1}L$ .

Ahora pruébalo.

Dave Clarke
fuente

¿Es suficiente dibujar una máquina de estado finito no determinista que acepte L y para probar esto?

w^{-} 1

$w^-1$

corium

@corium: No. Tendrá que hacer una prueba abstracta de y arbitrarias .

L

$L$

w

$w$

Raphael

la expresión regular

acepta

? - o?

(a + b)^{*} (a + b)

$(a+b)^* \;(a+b)$

L

$L$

corium

@ corium: No sé qué significa tu última declaración.

Dave Clarke

Un argumento muy breve arroja el famoso Teorema de MyHill y Nerode, que dice que un lenguaje es regular precisamente si tiene un número finito de cocientes. Entonces, para y tenemos , por lo tanto, tenemos menos cocientes para que para , en particular si solo tiene muchos cocientes, para $w \in X^{\ast}$ $L \subseteq X^{\ast}$ $u^{-1}(w^{-1}L) = (wu)^{-1}L$ $w^{-1}L$ $L$ $L$ también tenemos finitamente muchos. $w^{-1}L$

StefanH
fuente