Page 120 - LENGUAJES FORMALES AUTOMATAS Y COMPILADOS
P. 120
120
Jerarquías de máquinas y gramáticas
Para continuar, se identificarán las principales máquinas a ser estudiadas y luego se tratará el
vínculo entre estas máquinas y las diferentes gramáticas reconocidas por la jerarquía de Chomsky.
Al remitirse a su historia se comprueba que las máquinas abstractas presentadas hasta ahora
tuvieron como objetivo inicial el análisis de la computabilidad de funciones, así como el cálculo
y evaluación de la complejidad de algoritmos.
Es en esta última aplicación que importa precisar el diferente rol que tienen las gramáticas y las
máquinas o autómatas: las primeras son metalenguajes destinados a la generación de los lenguajes
formales y las últimas son modelos de entidades reconocedoras de esos lenguajes.
Recuérdese que se habla de isomorfismo entre dos estructuras cuando el estudio de cada una
puede reducirse al de la otra, lo que brinda dos puntos de vista diferentes sobre una misma
cuestión.
