Fundamentos de Gramáticas Formales: La Jerarquía de Chomsky y Tipos de Lenguajes
Clasificado en Informática
Escrito el en 
español con un tamaño de 3,57 KB
Definición y Estructura de las Gramáticas Formales
Una gramática formal es un mecanismo esencial para generar las cadenas que pertenecen a un lenguaje o para formar correctamente las frases de dicho lenguaje. Se define como un conjunto de reglas que, aplicadas a partir de un único símbolo inicial, son capaces de generar todas sus cadenas.
Estructura Formal de una Gramática
Formalmente, una gramática $G$ se define como una cuádrupla $G = (V, \Sigma, R, S)$, donde:
- V: Es un alfabeto de variables (símbolos no terminales).
- \Sigma: Es un alfabeto de constantes (símbolos terminales).
- R: Es el conjunto finito de reglas o producciones. Es un subconjunto de $V \times (\Sigma \cup V)^*$.
- S: Es el símbolo inicial, un elemento de $V$.
Una cadena $w \in \Sigma^*$ (es decir, una cadena formada exclusivamente por terminales) es derivable a partir de una gramática $G$ si existe una secuencia de pasos de derivación que la produce.
El lenguaje generado por una gramática $G$, denotado como $L(G)$, es igual al conjunto de todas las palabras derivables a partir de su símbolo inicial.
La Jerarquía de Chomsky: Clasificación de Gramáticas
El lingüista Noam Chomsky propuso varias formas estándares de reglas que se asocian a diversas clases de lenguajes. Estas clases están ordenadas de manera jerárquica, lo que implica que los lenguajes más primitivos están incluidos en los más complejos.
Gramáticas Regulares o de Tipo 3
Son las gramáticas más restrictivas y simples. Son capaces de describir los lenguajes regulares.
Las reglas de producción son de la forma:
- $A \to aB$
- $A \to a$
Donde $A$ y $B$ son variables (no terminales) y $a$ es un símbolo terminal (constante).
Formalmente, una gramática regular se define como una cuádrupla $(\Sigma_T, \Sigma_N, S, P)$, donde:
- $\Sigma_T$: Es un conjunto no vacío de símbolos terminales o constantes.
- $\Sigma_N$: Es un conjunto no vacío de símbolos no terminales o variables.
- $S$: Es el símbolo inicial, donde $S \in \Sigma_N$.
- $P$: Son las reglas o producciones.
La gramática regular, como toda gramática, es un metalenguaje que genera lenguajes.
Gramáticas Libres de Contexto (GLC) o de Tipo 2
Estas gramáticas producen los lenguajes libres de contexto (LLC).
Las reglas de producción son de la forma:
- $X \to \alpha$
Donde $X$ es una variable (no terminal) y $\alpha$ es una cadena que puede contener variables y terminales.
Gramáticas Sensitivas al Contexto (GSC) o Dependientes del Contexto, o de Tipo 1
Las reglas de producción son de la forma:
- $\alpha A \beta \to \alpha \Gamma \beta$
Donde $A$ es una variable, y $\alpha$, $\beta$ y $\Gamma$ son cadenas cualesquiera que pueden contener variables y terminales. La restricción clave es que la longitud de la cadena resultante debe ser mayor o igual que la longitud de la cadena original.
Gramáticas No Restringidas o de Tipo 0
Estas gramáticas generan los lenguajes llamados recursivamente enumerables.
Las reglas de producción son de la forma:
- $\alpha \to \beta$
Donde $\alpha$ es una cadena que no puede ser vacía, y $\beta$ es una cadena cualquiera de símbolos terminales y no terminales.