Probar que el lenguaje es regular o no regular

Deje que sea un lenguaje regular. Pruebalo: $L$

$L_{+--}=\left\{w: \exists_u |u|=2|w| \wedge wu\in L\right\}$

$L_{++-}=\left\{w: \exists_u 2|u|=|w| \wedge wu\in L \right\}$

$L_{-+-}=\left\{w:\exists_{u,v} |u|=|w|=|v| \wedge uwv\in L\right\}$

son regulares y:

$L_{+-+}=\left\{ uv:\exists_w |u|=|w|=|v| \wedge uwv\in L \right\}$

No es regular.

Me parece muy difícil. Supongo que 1-3 son similares (pero puedo estar equivocado), pero no sé cómo abordarlo. La idea general suele ser modificar la máquina de estados finitos para que acepte otro lenguaje. Pero esas construcciones son a menudo muy sofisticadas y todavía no se me ocurre solo. $L$

regular-languages xan
fuente

posible duplicado de ¿Cómo demostrar que un idioma no es regular?

Bartosz Przybylski

¡No estoy seguro de que sus afirmaciones sean correctas porque, según el teorema de Myhill – Nerode, los primeros tres idiomas tienen infinitas clases de equivalencia! para el primero: tomar

w_{i}

$w_i$ ser el i-ésimo en

L_{+ - -}

$L_{+--}$ y

w_{i + 1}

$w_{i+1}$ ser la (i + 1) -ésima palabra entonces por cada uno que pueda elegir

u_{i}

$u_i$ para mostrar que existe una palabra que separa las clases de

w_{i}

$w_i$ y

w_{i + 1}

$w_{i+1}$

Fayez Abdlrazaq Deab

@Fayez ¿Qué pasa si, por ejemplo,

L = Σ^{*}

$L=\Sigma^*$ ? Entonces

L_{+ - -} = Σ^{*}

$L_{+--} = \Sigma^*$ tiene solo una clase de equivalencia. Revise su prueba y vea qué sale mal.

Yuval Filmus

@Bartek y cualquier otro votante para cerrar: la mitad de la pregunta es en realidad sobre probar que ciertas operaciones en idiomas conservan la propiedad de ser regulares.

Yuval Filmus

Respuestas:

Aquí hay una prueba de que el idioma $L_0 = \{ w : \exists_u |u|=|w| \land uw \in L \}$ es regular Se puede modificar para mostrar que los primeros tres en su lista son regulares. (Tenga en cuenta que cambié $wu$ a $uw$ .) Dado un DFA para $L$ , creamos un NFA para $L_0$ . Lo primero que hace la NFA es adivinar (tome un $\epsilon$ mover) un estado $q$ , cuya semántica prevista es el estado para el que DFA $L$ termina después de leer $u$ . A continuación, ejecuta simultáneamente dos copias del DFA para $L$ , uno que comienza en el estado inicial y el otro que comienza en $q$ . Al leer un símbolo $a$ , se mueve de acuerdo con un símbolo arbitrario en el primero, y se mueve de acuerdo con $a$ en el segundo. Un estado acepta si la primera copia está en estado $q$ y el segundo está en un estado de aceptación.

Para el último, considere el idioma $L= a^+ b^+ c^+$ y se cruzan $L_{+-+}$ con $a^+ c^+$ .

Yuval Filmus
fuente

No veo eso

L = a^{+} b^{+} c^{+} \Rightarrow L_{+ - +} \cap a^{+} c^{+} = {a^{n} c^{m} : n + m \equiv_{2} 0}

$L=a^+b^+c^+ \Rightarrow L_{+-+} \cap a^+c^+=\left\{ a^n c^m: n+m\equiv_2 0 \right\}$ , que es claramente un lenguaje regular. Pero supongo que estoy equivocado :) ¿Puedes señalarme la dirección correcta?

xan

He logrado modificar su construcción de

L_{0}

$L_0$ e incluso eliminar

ε

$\varepsilon$ se mueve para que se vuelva más elegante (en mi opinión). Así que los primeros tres problemas resueltos y gracias por eso! :) Pero lo único que te pido es que aclares el final y mis preocupaciones en el comentario anterior. Estaría muy agradecido.

xan

Cuando calculo

L_{+ - +} \cap a^{+} c^{+}

$L_{+-+} \cap a^+ c^+$ Tengo algo mas. Tenga en cuenta que cada palabra en

L

$L$ debe contener un

b

$b$ .

Yuval Filmus

Lo siento, pero no sé cómo calcular

L_{+ - +} \cap a^{+} c^{+}

$L_{+-+}\cap a^+c^+$ . Supongo que el resultado es

{a^{n} c^{n} : n \in N}

$\left\{ a^n c^n: n\in\mathbb{N}\right\}$ lo que nos da lo que queremos, pero no sé cómo justificar eso.

xan

Ok, puedo ver ahora :-)

xan