Jerarquía de Chomsky: definición y clasificación de gramáticas (tipos 0–3)

Descubre la jerarquía de Chomsky: definición clara y clasificación práctica de gramáticas tipos 0–3, ejemplos y aplicaciones en informática teórica.

La jerarquía de Chomsky es un concepto de la informática teórica. Noam Chomsky observó las gramáticas del lenguaje regular y las clasificó en cuatro niveles, numerados del 0 al 3.

El grupo 0 consiste en expresiones regulares sin restricciones, mientras que los grupos 1 a 3 contienen restricciones. Las gramáticas de los niveles superiores también satisfacen las restricciones de todos los niveles inferiores. El concepto se desarrolló en los años 50.

Definición y clasificación (tipos 0–3)

La jerarquía de Chomsky clasifica las gramáticas formales según las restricciones que imponen sus reglas de producción. De forma resumida:

• Tipo 0 (gramáticas sin restricciones o de frases): las producciones pueden ser de la forma α → β con α y β cadenas de símbolos (al menos α no vacía). Generan los lenguajes recursivamente enumerables, equivalentes a los lenguajes reconocibles por una máquina de Turing.
• Tipo 1 (gramáticas sensibles al contexto): producciones con la forma αAβ → αγβ donde A es un no terminal y γ no es la cadena vacía. Generan los lenguajes sensibles al contexto, reconocidos por autómatas linealmente acotados (LBA).
• Tipo 2 (gramáticas libres de contexto, CFG): producciones de la forma A → γ, con A un no terminal. Generan los lenguajes libre de contexto, equivalentes a los aceptados por autómatas con pila (PDA).
• Tipo 3 (gramáticas regulares): producciones muy restringidas (por ejemplo A → aB, A → a o A → ε en algunas definiciones). Generan los lenguajes regulares, equivalentes a los aceptados por autómatas finitos o descritos por expresiones regulares.

Relación entre niveles

Existe una inclusión estricta de conjuntos de lenguajes:

• Lenguajes regulares ⊂ Lenguajes libres de contexto ⊂ Lenguajes sensibles al contexto ⊂ Lenguajes recursivamente enumerables.
• Esto significa que toda gramática tipo 3 cumple las restricciones de tipo 2, toda tipo 2 cumple las de tipo 1, y así sucesivamente.

Relación con autómatas y ejemplos

• Tipo 3 (regulares): correspondencia con autómatas finitos deterministas y no deterministas (DFA/NFA). Ejemplo: L = { a^* b^* } con una gramática regular que genera cualquier número de a seguido de cualquier número de b.
• Tipo 2 (libre de contexto): correspondencia con autómatas con pila (PDA). Ejemplo clásico no regular pero context-free: L = { a^n b^n | n ≥ 0 } generado por S → a S b | ε.
• Tipo 1 (sensibles al contexto): aceptados por autómatas linealmente acotados. Un ejemplo típico de lenguaje que no es libre de contexto pero sí sensible al contexto es L = { a^n b^n c^n | n ≥ 1 }.
• Tipo 0 (recursivamente enumerable): equivalen a lo que una máquina de Turing puede reconocer. Ejemplo conceptual: el conjunto de descripciones <M,w> de máquinas de Turing M que aceptan la entrada w.

Propiedades importantes

• Normalizaciones: Para gramáticas libres de contexto existen formas normales muy usadas en teoría y en algoritmos: la Forma Normal de Chomsky (CNF) y la Forma Normal de Greibach (GNF), que facilitan pruebas y análisis (por ejemplo el algoritmo CYK usa CNF).
• Cierre bajo operaciones: cada clase tiene distintas propiedades de cierre. Los lenguajes regulares y los context-free son cerrados bajo varias operaciones básicas (unión, concatenación, estrella), aunque los CFL no son cerrados en general bajo intersección ni complemento. Los lenguajes sensibles al contexto son cerrados bajo complementación (resultado profundo en teoría de la complejidad), unión e intersección.
• Decidibilidad: muchos problemas son decidibles para gramáticas regulares y libres de contexto (por ejemplo el problema de pertenencia: si una cadena pertenece a una CFL hay algoritmos eficientes; CYK decide pertenencia en tiempo polinómico y existen analizadores lineales para casos deterministas). Para tipo 0, el problema de pertenencia es semidecidible: si una cadena pertenece a la gramática, una máquina de Turing que reconoce el lenguaje lo aceptará eventualmente, pero no siempre existe un procedimiento que termine si la cadena no pertenece.

Aplicaciones y contexto histórico

La jerarquía de Chomsky es una herramienta fundamental para entender la potencia expresiva de distintos sistemas formales. Sus aplicaciones prácticas incluyen:

• Diseño de compiladores y análisis sintáctico (uso intensivo de gramáticas libres de contexto y sus formas normales).
• Expresiones regulares y análisis léxico (lenguajes regulares).
• Teoría de la computación y complejidad (relación entre clases de gramáticas y modelos de cómputo como máquinas de Turing o LBA).
• Lingüística teórica, donde el propio Chomsky motivó parte de la investigación originalmente.

El concepto fue introducido por Noam Chomsky en la década de 1950, en artículos que establecieron los fundamentos formales para comparar la expresividad de distintos tipos de gramáticas.

En resumen, la jerarquía de Chomsky ofrece un marco ordenado y útil para clasificar gramáticas y lenguajes según las restricciones en sus reglas de producción, y relaciona esas clases con modelos de cálculo concretos y propiedades algorítmicas.

Preguntas y respuestas

P: ¿Qué es la jerarquía de Chomsky?

P: ¿Quién desarrolló la jerarquía de Chomsky?

P: ¿Cuáles son los cuatro niveles de la jerarquía de Chomsky?

P: ¿Las gramáticas de los niveles superiores satisfacen las restricciones de todos los niveles inferiores?

P: ¿Cuándo se desarrolló el concepto de jerarquía de Chomsky?

P: ¿Cuál es el objetivo de la jerarquía de Chomsky?

P: ¿Qué importancia tiene la jerarquía de Chomsky en informática?

Búsqueda por letra