Gramática formal

De Wikipedia, la enciclopedia libre

Una gramática formal es objeto o modelo matemático que permite especificar un lenguaje o lengua, es decir, es el conjunto de reglas capaces de generar todas las posibilidades combinatorias de ese lenguaje, ya sea éste un lenguaje formal o un lenguaje natural.

La expresión «gramática formal» tiene dos sentidos:

gramática de un lenguaje formal.
descripción formal de parte de la gramática de un lenguaje natural.

Cuando nos referimos a lenguaje natural estas reglas combinatorias reciben el nombre de sintaxis, y son inconscientes.

Hay distintos tipos de gramáticas formales que generan lenguajes formales (véase la Jerarquía de Chomsky).

Imaginemos una gramática con estas dos reglas:

1. A → bAc 2. A → de

La idea es sustituir el símbolo inicial de la izquierda por otros símbolos aplicando las reglas. El lenguaje al cual representa esta gramática es el conjunto de cadenas de símbolos que pueden ser generados de esta manera: en este caso, por ejemplo:

A → bAc → bbAcc → bbbAccc → bbbdeccc.

El elemento en mayúsculas es el símbolo inicial. Los elementos en minúsculas son símbolos terminales. Las cadenas de la lengua son aquellas que solo contienen elementos terminales, como por ejemplo: bbbdeccc, de, bdec, ... Estas serían tres posibles realizaciones del lenguaje cuya gramática hemos definido con dos reglas. Para comprender mejor el concepto pondremos algunas reglas de la gramática castellana:

Una FRASE se puede componer de SUJETO + PREDICADO
$O = S N + S V$
Un SUJETO se puede componer de un ARTÍCULO + NOMBRE o SUBSTANTIVO (núcleo) + Complementos
$S N = D e t + N + C$
Un PREDICADO se puede componer de un VERBO conjugado
$S V = A u x + G V$
Un ARTICULO puede ser la palabra "el"
Un NOMBRE o SUBSTANTIVO puede ser "niño"
etc... [Véase Reglas de rescritura]

Vemos que existen unas definiciones especiales como FRASE, SUJETO, etc... que no aparecen en la frase final formada. Son unas entidades abstractas denominadas Categorías Sintácticas que no son utilizables en una frase. Las categorías sintácticas definen la estructura del lenguaje representando porciones más o menos grandes de las frases. Existe una jerarquía interna entre las categorías sintácticas. La categoría superior sería la FRASE que representa una oración válida en lengua castellana. Por debajo de ella se encuentran sus componentes. Ninguna de estas categorías dan lugar a frases válidas solo la categoría superior. Al finalizar toda la jerarquía llegamos a las palabras que son las únidades mínimas con significado que puede adoptar una frase. Aplicando las jerarquía y sustituyendo elementos, llegamos al punto en donde todas las categorías sintácticas se han convertido en palabras, obteniendo por tanto una oración VALIDA. (Como por ejemplo: El niño corre). Este proceso se llama producción o generación. En resumen:

[editar] Elementos constituyentes

Una gramática formal es un modelo matemático compuesto por una serie de categorías sintácticas que se combinan entre sí por medio de unas reglas sintácticas que definen cómo se crea una categoría sintáctica por medio de otras o símbolos de la gramática.
Existe una única categoría superior que denota cadenas completas y válidas.

[editar] Mecanismos de Especificación

Por medio de estos elementos constituyentes se define un mecanismo de especificación consistente en repetir el mecanismo de sustitución de una categoría por sus constituyentes en función de las reglas comenzando por la categoría superior y finalizando cuando la oración ya no contiene ninguna categoría.

De esta forma, la gramática puede generar o producir cada una de las cadenas del lenguaje correspondiente y solo estas cadenas.

[editar] Definición

Una Gramática Formal es una cuádrupla $G = (N, T, P, S) \,$ donde:

$N$ es un alfabeto de símbolos no terminales (variables).
$T$ es un alfabeto de símbolos terminales (constantes).
Debe cumplirse que $N \cap T = \emptyset$ . denotaremos con $\Sigma = N \cup T$ el alfabeto de la gramática.
$S \in N$ es el símbolo inicial o axioma de la gramática.
$P \,$ es el conjunto de reglas de producción, de la forma $P = \,$ { α → β | α $\in \Sigma^* N \Sigma^*$ β $\in \Sigma^*$ }

Es decir, la cadena α debe contener al menos una variable, que puede estar rodeada de un contexto.

[editar] Derivaciones

Sea $G = (N, T, P, S)$ una gramática, y sean α, β, δ, φ, ρ, ... palabras de $Σ *$ . Entonces

β se deriva de α en un paso de derivación, y lo denotamos con α $\Rightarrow$ β si existen dos cadenas $\phi_1, \phi_2 \in \Sigma^*$ , y una producción δ → ρ tales que α = $φ 1$ δ $φ 2$ , y β = $φ 1$ ρ $φ 2$

Notamos con $\Rightarrow^*$ al cierre reflexivo y transitivo de $\Rightarrow$ . Es decir α $\Rightarrow^*$ β denota a una secuencia de derivaciones en un número arbitrario de pasos desde α hasta β.

$x \in \Sigma^*$ es una forma sentencial de $G$ , si puede obtenerse la siguiente secuencia de derivaciones $S \Rightarrow^* x$ . En el caso particular de que $x \in T^*$ se dice que x es una sentencia