Gramáticas formales y la jerarquía de Chomsky: tipos de lenguajes
Resumen
El documento explica qué es una gramática formal, cómo se define formalmente como una cuádrupla de variables, terminales, reglas y símbolo inicial, y qué cadenas genera. Después presenta la jerarquía de Chomsky, con los cuatro tipos de gramáticas (regulares, libres de contexto, sensitivas al contexto y no restringidas) y los lenguajes que describe cada una.
Puntos clave
- Una gramática formal G se define como la cuádrupla G = (V, Σ, R, S), con variables V, terminales Σ, reglas R y símbolo inicial S.
- El lenguaje generado por G, L(G), es el conjunto de todas las palabras derivables a partir de su símbolo inicial.
- La jerarquía de Chomsky ordena las gramáticas en cuatro tipos, de modo que los lenguajes más simples están incluidos en los más complejos.
- Las gramáticas regulares (tipo 3) tienen reglas de la forma A → aB o A → a y describen los lenguajes regulares.
- Las gramáticas libres de contexto (tipo 2) tienen reglas de la forma X → α y generan los lenguajes libres de contexto.
- Las gramáticas sensitivas al contexto (tipo 1) cumplen que la longitud de la cadena resultante no es menor que la de la original.
- Las gramáticas no restringidas (tipo 0) generan los lenguajes recursivamente enumerables.
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.
Descargar
PDF Word HTMLPreguntas frecuentes
¿Qué es una gramática formal?
Es un conjunto de reglas que, aplicadas a partir de un único símbolo inicial, permiten generar todas las cadenas de un lenguaje. Formalmente se define como una cuádrupla G = (V, Σ, R, S).
¿Qué lenguajes describen las gramáticas regulares?
Las gramáticas regulares o de tipo 3 describen los lenguajes regulares. Son las más restrictivas, con reglas de la forma A → aB o A → a.
¿Qué restricción cumplen las gramáticas sensitivas al contexto?
Las reglas tienen la forma αAβ → αΓβ, y la longitud de la cadena resultante debe ser mayor o igual que la de la original.
¿Qué generan las gramáticas de tipo 0?
Generan los lenguajes recursivamente enumerables. Sus reglas son de la forma α → β, donde α no puede ser vacía.
Ponte a prueba
Tarjetas de repaso
Pulsa una tarjeta para ver la respuesta.
Test
Preguntas generadas con IA a partir del documento: comprueba las respuestas con el texto.