Page 20 - LENGUAJES FORMALES AUTOMATAS Y COMPILADOS

20

GRAMÁTICAS Y LENGUAJES FORMALES

El desarrollo de los ordenadores en la década de los 40, con la introducción de los programas en
la memoria principal y posteriormente con los lenguajes de programación de alto nivel, propician
la distinción entre lenguajes formales, con reglas sintácticas y semánticas rígidas, concretas y bien
definidas, de los lenguajes naturales como el inglés, donde la sintaxis y la semántica no se pueden
controlar fácilmente. Los intentos de formalizar los lenguajes naturales llevan a la construcción
de gramáticas como una forma de describir estos lenguajes, utilizando para ello reglas de
producción para construir las frases del lenguaje. Así las cosas, se establece que se puede entonces
caracterizar un lenguaje mediante las
Reglas de una gramática adecuada.

Noam Chomsky propone en 1956 tres modelos para la descripción de lenguajes,
que son la base de su futura jerarquía de los tipos de lenguajes (1959), que ayudo
también en el desarrollo de los lenguajes de programación. Chomsky establecido
una clasificación de gramáticas de acuerdo con el formato de sus producciones y
distinguió cuatro clases fundamentales de lenguajes y relaciones de inclusión entre
ellas.
Noam Chomsky
La teoría de los lenguajes formales resulto tener una relación sorprendente con la teoría de
autómatas y la computabilidad. Paralelamente a la jerarquía de lenguajes existe otra equivalente
de máquinas abstractas, de tal forma que, a cada una de las clases de lenguajes definidas en la
jerarquía de Chomsky a partir de restricciones impuestas a las gramáticas, le corresponde un tipo
de maquina abstracta, que no es otra cosa que un método reconocedor para la descripción de
lenguajes. La relación la podemos observar en la siguiente relación.

LENGUAJE TIPO 0 → MÁQUINA DE TURING
.
LENGUAJE TIPO 1 → AUTÓMATAS LINEALMENTE ACOTADOS

LENGUAJE TIPO 2 → AUTÓMATAS CON PILA

LENGUAJE TIPO 3 → AUTÓMATAS FINITOS

Cada uno de estos tipos de máquinas es capaz de resolver problemas cada vez más complejos,
desde los autómatas finitos (que son los más simples) hasta las Máquinas de Turing que
determinan el límite de los procesos computables. Se puede llegar así, de una forma casi natural,
a considerar las Máquinas de Turing, establecidas casi 20 años antes, como maquinas
reconocedoras de los lenguajes estructurados por frases (tipo 0) e incluso a interpretar la tesis de
Turing en términos de que un sistema computacional nunca podrá efectuar un análisis sintáctico
de aquellos lenguajes que están por encima de los lenguajes estructurados por frases en la
jerarquía de Chomsky.