Page 54 - LENGUAJES FORMALES AUTOMATAS Y COMPILADOS

54

ENTREGA III

LENGUAJES REGULARES Y AUTOMATAS FINITOS

1- Lenguajes regulares y expresiones regulares
2- Autómatas finitos
3- Matriz de transición de estado

Uniones, intersecciones y complementos de los lenguajes regulares

Los (LR) se rigen por reglas de sintaxis y semántica más complejas y definidas y que finalmente
son manejadas por los computadores. Entramos a clasificar los lenguajes. Ya que los lenguajes
en sí son conjuntos de secuencias de símbolos y cada uno comparte una cierta propiedad. Misma
que debe establecer sea través de la gramática la clasificación de estos lenguajes se dio en 1959,
por Chomsky, pero esta clasificación al final son realmente 4 familias de gramáticas. Estas
gramáticas atendiendo a sus reglas de producción general determinan los lenguajes y de allí la
clasificación anteriormente vista.

Formalmente se puede definir una gramática, como una cuádrupla así:

G = (VN, VT, S, P) en donde:

VN: conjunto finito de no terminales.

VT: conjunto finito de terminales.
S: es el símbolo inicial y debe ser un elemento del conjunto de no terminales.

P: es un conjunto finito de reglas de rescritura. También se le denomina producciones, porque a
través de estas reglas se generan las palabras que acepta el lenguaje.

En general, los lados derechos e izquierdos de las reglas de reescritura de producción de una
gramática pueden ser cualquier combinación disímbolos terminales y no terminales, siempre y
cuando el lado izquierdo contenga por lo menos un no terminal.

Atendiendo a la clasificación de Chomsky el tipo 3, corresponde a gramáticas regulares y los
lenguajes generados por estas gramáticas se llaman “lenguajes regulares”, y el conjunto de todos
estos lenguajes es la clase.

L3, que es la clase más pequeña, e incluye a los lenguajes más simples.

A continuación, otro esquema que se relaciona con la clasificación de Chomsky ya vista, que está
asociada al tipo de lenguaje, gramática, tipo de máquina y tipo de problemas que atiende.