Gramática formal

Supongamos que tenemos las siguientes reglas de producción:

1.${\displaystyle S\rightarrow aSb}$

2.${\displaystyle S\rightarrow ba}$

Luego comenzamos con S y podemos elegir una regla para aplicarle. Si elegimos la regla 1, obtenemos la cadena aSb . Si volvemos a elegir la regla 1, reemplazamos S con aSb y obtenemos la cadena aaSbb . Si ahora elegimos la regla 2, reemplazamos S con ba y obtenemos la cadena aababb , y hemos terminado. Podemos escribir esta serie de elecciones de forma más breve, usando símbolos:${\displaystyle S\Rightarrow aSb\Rightarrow aaSbb\Rightarrow aababb}$.

El lenguaje de la gramática es el conjunto infinito.${\displaystyle \{a^{n}bab^{n}\mid n\geq 0\}=\{ba,abab,aababb,aaababbb,\dotsc \}}$, dónde${\displaystyle a^{k}}$es${\displaystyle a}$repetido${\displaystyle k}$veces (y${\displaystyle n}$en particular representa el número de veces que se ha aplicado la regla de producción 1). Esta gramática es libre de contexto (solo aparecen no terminales simples como lados izquierdos) y no ambigua.

Supongamos que las reglas son estas:

1.${\displaystyle S\rightarrow a}$

2.${\displaystyle S\rightarrow SS}$

3.${\displaystyle aSa\rightarrow b}$

Esta gramática no es libre de contexto debido a la regla 3 y es ambigua debido a las múltiples formas en que la regla 2 puede usarse para generar secuencias de${\displaystyle S}$s.

Sin embargo, el lenguaje que genera es simplemente el conjunto de todas las cadenas no vacías que consisten en${\displaystyle a}$s y/o${\displaystyle b}$s. Esto es fácil de ver: para generar un${\displaystyle b}$de un${\displaystyle S}$, use la regla 2 dos veces para generar${\displaystyle SSS}$, luego la regla 1 dos veces y la regla 3 una vez para producir${\displaystyle b}$. Esto significa que podemos generar secuencias no vacías arbitrarias de${\displaystyle S}$y luego reemplace cada uno de ellos con${\displaystyle a}$o${\displaystyle b}$como queramos.

Ese mismo lenguaje puede generarse alternativamente mediante una gramática no ambigua y libre de contexto; por ejemplo, la gramática regular con reglas.

1.${\displaystyle S\rightarrow aS}$

2.${\displaystyle S\rightarrow bS}$

3.${\displaystyle S\rightarrow a}$

4.${\displaystyle S\rightarrow b}$

En la formalización clásica de las gramáticas generativas propuesta por primera vez por Noam Chomsky en la década de 1950, ^{[ 2 ] [ 3 ]} una gramática G consta de los siguientes componentes:

• Un conjunto finito N de símbolos no terminales , que es disjunto con las cadenas formadas a partir de G.
• Un conjunto finito${\displaystyle \Sigma }$de símbolos terminales que es disjunto de N.
• Un conjunto finito P de reglas de producción , cada regla de la forma

${\displaystyle (\Sigma \cup N)^{*}N(\Sigma \cup N)^{*}\rightarrow (\Sigma \cup N)^{*}}$

dónde${\displaystyle {*}}$es el operador estrella de Kleene y${\displaystyle \cup }$denota la unión de conjuntos . Es decir, cada regla de producción mapea una cadena de símbolos a otra, donde la primera cadena (la "cabeza") contiene un número arbitrario de símbolos siempre que al menos uno de ellos sea un no terminal. En el caso de que la segunda cadena (el "cuerpo") consista únicamente en la cadena vacía , es decir, que no contenga ningún símbolo , puede denotarse con una notación especial (a menudo${\displaystyle \Lambda }$, e o${\displaystyle \epsilon }$) para evitar confusiones. Dicha regla se denomina regla de borrado . ^{[ 4 ]}

• Un símbolo distinguido${\displaystyle S\in N}$Ese es el símbolo de inicio , también llamado símbolo de oración .

Una gramática se define formalmente como la tupla${\displaystyle (N,\Sigma ,P,S)}$. Dicha gramática formal se denomina a menudo sistema de reescritura o gramática de estructura de frases en la literatura. ^{[ 5 ] [ 6 ]}

El funcionamiento de una gramática se puede definir en términos de relaciones sobre cadenas de caracteres:

• Dada una gramática${\displaystyle G=(N,\Sigma ,P,S)}$, la relación binaria${\displaystyle {\underset {G}{\Rightarrow }}}$(pronunciado como "G deriva en un paso") en cuerdas en${\displaystyle (\Sigma \cup N)^{*}}$se define por:

  ${\displaystyle x{\underset {G}{\Rightarrow }}y\iff \exists u,v,p,q\in (\Sigma \cup N)^{*}:(x=upv)\wedge (p\rightarrow q\in P)\wedge (y=uqv)}$

• la relación${\displaystyle {\overset {*}{\underset {G}{\Rightarrow }}}}$(pronunciado como G deriva en cero o más pasos ) se define como el cierre transitivo reflexivo de${\displaystyle {\underset {G}{\Rightarrow }}}$
• aLa forma oracional es un miembro de${\displaystyle (\Sigma \cup N)^{*}}$que se puede derivar en un número finito de pasos desde el símbolo inicial${\displaystyle S}$; es decir, una forma oracional es un miembro de${\displaystyle \left\{w\in (\Sigma \cup N)^{*}\mid S{\overset {*}{\underset {G}{\Rightarrow }}}w\right\}}$. Una forma sentencial que no contiene símbolos no terminales (es decir, es un miembro de${\displaystyle \Sigma ^{*}}$) se llama oración . ^{[ 7 ]}
• el idioma de${\displaystyle G}$, denotado como${\displaystyle {\boldsymbol {L}}(G)}$, se define como el conjunto de oraciones construidas por${\displaystyle G}$.

La gramática${\displaystyle G=(N,\Sigma ,P,S)}$es efectivamente el sistema semi-Thue${\displaystyle (N\cup \Sigma ,P)}$, reescribiendo cadenas exactamente de la misma manera; la única diferencia radica en que distinguimos símbolos no terminales específicos , que deben ser reemplazados en las reglas de reescritura, y solo nos interesan las reescrituras desde el símbolo inicial designado.${\displaystyle S}$a cadenas sin símbolos no terminales.

Para estos ejemplos, los lenguajes formales se especifican utilizando la notación de construcción de conjuntos .

Consideremos la gramática${\displaystyle G}$dónde${\displaystyle N=\left\{S,B\right\}}$,${\displaystyle \Sigma =\left\{a,b,c\right\}}$,${\displaystyle S}$es el símbolo de inicio, y${\displaystyle P}$Consta de las siguientes reglas de producción:

1.${\displaystyle S\rightarrow aBSc}$

2.${\displaystyle S\rightarrow abc}$

3.${\displaystyle Ba\rightarrow aB}$

4.${\displaystyle Bb\rightarrow bb}$

Esta gramática define el idioma.${\displaystyle L(G)=\left\{a^{n}b^{n}c^{n}\mid n\geq 1\right\}}$dónde${\displaystyle a^{n}}$denota una cadena de n caracteres consecutivos${\displaystyle a}$'s. Por lo tanto, el lenguaje es el conjunto de cadenas que constan de 1 o más${\displaystyle a}$'s, seguido del mismo número de${\displaystyle b}$'s, seguido del mismo número de${\displaystyle c}$'s.

Algunos ejemplos de la derivación de cadenas en${\displaystyle L(G)}$son:

(Sobre la notación:${\displaystyle P{\underset {i}{\Rightarrow }}Q}$(El texto dice: "La cadena P genera la cadena Q mediante la producción i ", y la parte generada se indica cada vez en negrita).

Una gramática libre de contexto es una gramática en la que el lado izquierdo de cada regla de producción consta de un único símbolo no terminal. Esta restricción no es trivial; no todos los lenguajes pueden generarse mediante gramáticas libres de contexto. Aquellos que sí pueden se denominan lenguajes libres de contexto .

El idioma${\displaystyle L(G)=\left\{a^{n}b^{n}c^{n}\mid n\geq 1\right\}}$La definición anterior no es un lenguaje libre de contexto, y esto se puede probar rigurosamente utilizando el lema de bombeo para lenguajes libres de contexto , pero por ejemplo el lenguaje${\displaystyle \left\{a^{n}b^{n}\mid n\geq 1\right\}}$(al menos 1${\displaystyle a}$seguido por el mismo número de${\displaystyle b}$'s) es independiente del contexto, ya que puede definirse mediante la gramática.${\displaystyle G_{2}}$con${\displaystyle N=\left\{S\right\}}$,${\displaystyle \Sigma =\left\{a,b\right\}}$,${\displaystyle S}$el símbolo de inicio y las siguientes reglas de producción:

1.${\displaystyle S\rightarrow aSb}$

2.${\displaystyle S\rightarrow ab}$

Un lenguaje libre de contexto puede ser reconocido en${\displaystyle O(n^{3})}$tiempo ( ver notación Big O ) por un algoritmo como el reconocedor de Earley y en un tiempo subcúbico por algoritmos rápidos de multiplicación de matrices . ^{[ 9 ]} Es decir, para cada lenguaje libre de contexto, se puede construir una máquina que toma una cadena como entrada y determina en${\displaystyle O(n^{3})}$tiempo si la cadena es miembro del lenguaje, donde${\displaystyle n}$es la longitud de la cadena. ^{[ 10 ]} Los lenguajes libres de contexto deterministas son un subconjunto de lenguajes libres de contexto que pueden ser reconocidos en tiempo lineal. ^{[ 11 ]} Existen varios algoritmos que se dirigen a este conjunto de lenguajes o a algún subconjunto del mismo.

En las gramáticas regulares , el lado izquierdo vuelve a ser un único símbolo no terminal, pero ahora el lado derecho también está restringido. El lado derecho puede ser la cadena vacía, un único símbolo terminal o un único símbolo terminal seguido de un símbolo no terminal, pero nada más. (A veces se utiliza una definición más amplia: se permiten cadenas más largas de terminales o de símbolos no terminales sin nada más, lo que facilita la designación de los lenguajes sin dejar de definir la misma clase de lenguajes).

El idioma${\displaystyle \left\{a^{n}b^{n}\mid n\geq 1\right\}}$La definición anterior no es regular, pero el lenguaje${\displaystyle \left\{a^{n}b^{m}\mid m,n\geq 1\right\}}$(al menos 1${\displaystyle a}$seguido de al menos 1${\displaystyle b}$(donde los números pueden ser diferentes) es, como puede definirse mediante la gramática${\displaystyle G_{3}}$con${\displaystyle N=\left\{S,A,B\right\}}$,${\displaystyle \Sigma =\left\{a,b\right\}}$,${\displaystyle S}$el símbolo de inicio y las siguientes reglas de producción:

1. ${\displaystyle S\rightarrow aA}$
2. ${\displaystyle A\rightarrow aA}$
3. ${\displaystyle A\rightarrow bB}$
4. ${\displaystyle B\rightarrow bB}$
5. ${\displaystyle B\rightarrow \epsilon }$

Todos los lenguajes generados por una gramática regular pueden ser reconocidos en${\displaystyle O(n)}$tiempo por una máquina de estados finitos. Aunque en la práctica las gramáticas regulares se expresan comúnmente mediante expresiones regulares , algunas formas de expresiones regulares utilizadas en la práctica no generan estrictamente los lenguajes regulares y no muestran un rendimiento de reconocimiento lineal debido a esas desviaciones.

Se han desarrollado numerosas extensiones y variaciones de la jerarquía original de gramáticas formales de Chomsky, tanto por lingüistas como por informáticos, generalmente con el fin de aumentar su poder expresivo o de facilitar su análisis o interpretación. Algunas formas de gramáticas desarrolladas incluyen:

• Las gramáticas de adjunción de árboles aumentan la expresividad de las gramáticas generativas convencionales al permitir que las reglas de reescritura operen en árboles de análisis sintáctico en lugar de solo cadenas. ^{[ 12 ]}
• Las gramáticas de afijos ^{[ 13 ]} y las gramáticas de atributos ^{[ 14 ] [ 15 ]} permiten que las reglas de reescritura se amplíen con atributos y operaciones semánticas, útiles tanto para aumentar la expresividad gramatical como para construir herramientas prácticas de traducción de idiomas.

Una gramática recursiva es aquella que contiene reglas de producción recursivas . Por ejemplo, una gramática para un lenguaje libre de contexto es recursiva por la izquierda si existe un símbolo no terminal A que, al pasar por las reglas de producción, genera una cadena con A como el símbolo más a la izquierda. ^{[ 16 ]} Un ejemplo de gramática recursiva es una cláusula dentro de una oración separada por dos comas. ^{[ 17 ]} Todos los tipos de gramáticas en la jerarquía de Chomsky pueden ser recursivos.