Tema 3. Lenguajes y teoremas de equivalencia entre lenguajes producidos por gramáticas y lenguajes reconocidos por autómatas.

El lenguaje

es simplemente un conjunto de palabras. Así, {consecuencia} es un lenguaje (de una sola palabra), {los, tres, mosqueteros} es otro. Puesto que las secuencias fueron definidas en la sección de preliminares. Formalmente, la palabra es la secuencia de letras que la conforman. Los lenguajes son conjuntos, podemos efectuar con ellos todas las operaciones de los conjuntos (unión, intersección, diferencia)

Concepto de Expresión Regular

El objetivo de las Expresiones Regulares es representar todos los posibles lenguajes definidos sobre un alfabeto Σ. Para ello se utilizan: 

*Lenguajes primitivos: Lenguaje vacío, el lenguaje con la palabra vacía, y los lenguajes con los símbolos del alfabeto. 

*Operadores de composición: unión, concatenación, el cierre y los paréntesis.

Teoremas de Equivalencia

Mediante expresiones regulares se puede representar cualquier lenguaje regular.

* Representación de lenguajes regulares:

* Gramáticas lineales por la izquierda

* Gramáticas lineales por la derecha

* AFD

* AFND

Para ver ejemplos entrar a: http://www.ia.urjc.es/cms/sites/default/files/userfiles/file/GIC-MSAL/Tema4_ExpresionesRegulares.pdf

Teoremas 

Teorema 1
El conjunto de lenguajes reconocidos por autómatas finitos no deterministas coincide con el conjunto de lenguajes reconocidos por autómatas finitos deterministas.

Teorema 2
El conjunto de lenguajes regulares coincide con el conjunto de lenguajes reconocidos por autómatas finitos.

2.1 Para todo lenguaje regular existe una gramática regular que lo genera que puede expresarse mediante reglas de re-escritura en cuyos lados derechos nunca aparezca en solitario un símbolo terminal.

Teorema 3
El conjunto de lenguajes reconocidos por autómatas finitos coincide con el conjunto de lenguajes representados por expresiones regulares.

3.1 Todos los lenguajes con un número finito de cadenas son regulares.

3.2 El conjunto de cadenas aceptadas por un autómata finito puede ser infinito.

Teorema 4
Existen lenguajes no regulares.

Teorema 5
La unión de un conjunto finito de lenguajes regulares es un lenguaje regular.