Jerarquía de Chomsky

Revisión del 16:14 6 jul 2019 de Javiermartin jc (discusión | contribuciones) (Texto reemplazado: «<div align="justify">» por «»)
(dif) ← Revisión anterior | Revisión actual (dif) | Revisión siguiente → (dif)
Jerarquía de Chomsky
Información sobre la plantilla
Jerarquia Chomsky A.gif
Concepto:Sistema de definiciones que permite clasificar de 4 formas posibles los lenguajes formales ideado por Noam Chomsky.

Jerarquía de Chomsky. En Lingüística, Matemáticas e Informática dícese del sistema jerárquico de definiciones, ideado por Noam Chomsky en 1956 en el MIT para clasificar de manera matemática los lenguajes formales en cuatro categorías enumeradas de 0 a 3 y los mecanismos formalizadores como gramáticas formales, expresiones y autómatas para reconocer cada tipo.

También se conoce bajo el nombre de Clasificación de Chomsky o Jerarquía matemática de los lenguajes.

La Jerarquía de Chomsky.

Sea un lenguaje L definido por al menos una gramática G que cumple:

Desde el punto de vista conjuntual la jerarquía de Chomsky funciona como se ve en al gráfico:

  • Jerarquia Chomsky.gif.

De manera que todos los lenguajes de tipo 3 (LR) son también de tipo 2 (LLC) y los LLC son de tipo 1 (LDC) son de tipo 0 (LSR ó LRE).

Consecuencias.

La jerarquía de Chomsky no solo aporta un ordenamiento conjuntual de los lenguajes, sino que proporciona un mecanismo de clasificación basado en características relacionadas con las formas gramaticales mínimas de cada lenguaje en particular así como decide qué tipo de reconocedores mínimos servirían para determinar las cadenas válidas.

Tipo Nombre Forma de las producciones Tipo de autómata o reconocedor
0 LRE Irrestrictas Máquina de Turing
1 LDC X A y flecha x z y.gif Autómata linealmente acotado
2 LLC A flecha x.gif Autómata de pila
3 LR A flecha x B.gif
ó
A flecha x.gif
Autómata finito
Expresión regular

Hechos que se sostienen en la formalización de Alan Turing con sus autómatas que emulaban diversos procesos algoritmizables, modelos ya demostrados y aceptados en la naciente comunidad de especialistas en computadoras y matemáticas aplicadas a los ordenadores. Este aporte derivado de la visión estructuralista y matemática del momento de realización de esta teoría lingüística encontró su mayor sistema de aplicación en las ciencias de la computación y el desarrollo de las teorías y técnicas de desarrollo de lenguajes de programación y especificado y los compiladores e intérpretes que los procesen, dotándolos de un cuerpo teórico y abriendo las puertas a la gran diversidad de lenguajes de computadora que existen en la actualidad.

Fuentes.

  1. Tanembaum, A. Compilers: Principles, Tecniques, and Tools. Tomo 1. ACM Press. 5ta Edición.
  2. Conferencias de la Asignatura "Compilación 1" del Departamento de Ciencias de la Computación de la Universidad de Oriente. Santiago de Cuba, 2000.
  3. Jerarquía de Chomsky en Wikipedia. Consultado el 20 de febrero de 2012.