Es Este Lenguaje Regular o no?

Question

Tengo el lenguaje {4^(w⋅g)34^(g)|w,g∈NAT} sobre el alfabeto {0,1}.

Necesito saber si este lenguaje es reconocible, decidable, el contexto libre, regular o ninguno de estos.

¿Cómo puedo hacerlo o saber?

Gracias

Answer 1

Considere la posibilidad de cualquier cadena de la forma 4^a 3 4^b.Podemos encontrar w, g para nuestro a, b?Bien, sabemos que g debe ser igual a b, y , a continuación, podemos elegir w = a + g.Desde a, b y g son números naturales, por lo que debe de ser w;la respuesta es que sí, para cualquier cadena de la forma 4^a 3 4^b, tenemos una cadena en su idioma.

El lenguaje de todas las cadenas de la forma 4^a 3 4^b es descrito por la expresión regular 4* 3 4* y, como tal, su lenguaje es regular, el contexto libre, decidable y reconocible.

Supongamos que su lenguaje no regular;¿cómo podría saberlo?Usted podría utilizar la Myhill-Nerode teorema o el Lema de Bombeo para regular idiomas para derivar una contradicción de asumir el lenguaje fueron regulares.

Supongamos que el idioma no fuera de contexto libre.Usted podría utilizar el Lema de Bombeo para el contexto libre de idiomas para derivar una contradicción de asumir el lenguaje fueron contexto libre.

Por supuesto, si el lenguaje no fuera decidable o reconocible, podría probar que, en diversas formas.