Page 40 - LENGUAJES FORMALES AUTOMATAS Y COMPILADOS
P. 40
40
En el siguiente cuadro se esquematiza la relación entre lenguajes, gramáticas, máquinas abstractas
y problemas. Atendiendo al lenguaje o tipo del lenguaje, así mismo se asocia un tipo de autómata,
así las cosas, se definirán los lenguajes clasificados según Chomsky.
Gramáticas Lenguajes Máquinas Problemas
NO COMPUTABLES
Tipo 0 de Chomsky Recursivamente Máquinas de Turing Computables
Numerables
Lenguajes Autómatas lineales acotados
Tipo 1 de Chomsky sensibles al
contexto
Lenguajes Autómatas a pila
Tipo 2 de Chomsky independientes
del contexto
Tipo 3 de Chomsky Lenguajes Autómatas finitos Expresiones
regulares deterministas regulares
En estos tipos:
Tipo 3: gramáticas regulares que generan lenguajes regulares.
Tipo 2: gramáticas incontextuales o libres de contexto que generan lenguajes
incontextuales o también denominadas fuera de contexto.
Tipo 1: gramáticas contextuales o dependientes del contexto, que generan lenguajes
contextuales.
Tipo 0: gramáticas libres que generan lenguajes sin ningún tipo de restricción.
Cuanto menor es el tipo,
mayor es el poder expresivo
del lenguaje generado y más
complejidad tiene su
tratamiento por parte de una
máquina.
La clasificación completa
asociada a los problemas y
lenguajes.