Page 55 - LENGUAJES FORMALES AUTOMATAS Y COMPILADOS

55

Hay un teorema, válido expresar con motivo de este esquema que es Chomsky y su clasificación:
(jerarquía de Chomsky): dado un alfabeto ∑, el conjunto de los lenguajes regulares sobre ∑ está
incluido propiamente en el conjunto de los lenguajes libres de contexto y este a su vez está
incluido propiamente en el conjunto de los lenguajes sensibles al contexto, que finalmente está
incluido propiamente en el conjunto de lenguajes con estructura de frase. Esto es: L3 ⸦ L2 ⸦ L1
⸦ L0.
Entonces el tipo3 es: (gramáticas regulares).

Estas gramáticas regulares pueden ser a su vez de dos tipos a saber:

1- Lineales por la derecha, donde todas las producciones son de la forma:
A  BC
A  B
A  Λ
Donde: (A, C Є VN) Y (B Є VT)

2- Lineales por la izquierda, donde todas las producciones son de la forma:
A  CB
A  B
A  Λ
Donde: (A, C Є VN) Y (B Є VT)

Para cada gramática lineal por la derecha existe una gramática lineal por la izquierda que genera
el mismo lenguaje y viceversa.

Los lenguajes regulares son lenguajes formales que tienen las siguientes características:

1- Puede ser descrito mediante una expresión regular, esto es expresar de forma compacta
cómo son todas las cadenas de símbolos que le pertenecen. Es decir, en una sola expresión
general, describir como pueden ser las cadenas de símbolos que serán aceptadas o
reconocidas.
2- Puede ser generado por una gramática regular, esto es poder obtener todas las cadenas de