Gramática formal

Na Galipedia, a wikipedia en galego.

Unha gramática formal é un obxeto ou modelo matemático que permite especificar unha linguaxe ou lingua, é dicir, é o conxunto de regras capaces de xerar todalas posibilidades combinatorias desa linguaxe, xa sexa esta unha linguaxe formal ou unha linguaxe natural.

[editar] Introdución

A expresión «gramática formal» ten dous sentidos:

gramática dunha linguaxe formal.
descrición formal de parte da gramática dunha linguaxe natural.

Cando nos referimos a linguaxe natural estas regras combinatorias reciben o nome de sintaxe, e son inconscientes.

Hai distintos tipos de gramáticas formais que xeran linguaxes formais (véxase a Xerarquía de Chomsky).

Imaxinemos unha gramática con estas dúas regras:

1. A → bAc 2. A → de

A idea é substituír o símbolo inicial da esquerda por outros símbolos aplicando as regras. A linguaxe ao cal representa esta gramática é o conxunto de cadeas de símbolos que poden ser xerados deste xeito: neste caso, por exemplo:

A → bAc → bbAcc → bbbAccc → bbbdeccc.

O elemento en maiúsculas é o símbolo inicial. Os elementos en minúsculas son símbolos terminais. As cadeas da lingua son aquelas que só conteñen elementos terminais, por exemplo:

bbbdeccc, de, bdec, ... Estas serían tres posibles realizacións da linguaxe cuxa gramática definimos con dúas regras.

Para comprender mellor o concepto poremos algunhas regras da gramática galega:

Unha FRASE pódese compor de SUXEITO + PREDICADO
$O u = S N + S V$
Un SUXEITO pódese compor dun ARTIGO + NOMEE ou SUSTANTIVO (núcleo) + Complementos
$S N = D e t + N + C$
Un PREDICADO pódese compor dun VERBO conxugado
$S V = A u x + G V$
Un ARTICULO pode ser a palabra "o"
Un NOME ou SUBSTANTIVO pode ser "neno"
etc... [Véxase Regras de rescritura]

Vemos que existen unhas definicións especiais como FRASE, SUXEITO, etc... que non aparecen na frase final formada. Son unhas entidades abstractas denominadas Categorías Sintácticas que non son utilizables nunha frase.

As categorías sintácticas definen a estrutura da linguaxe representando porcións máis ou menos grandes das frases. Existe unha xerarquía interna entre as categorías sintácticas.

A categoría superior sería a FRASE que representa unha oración válida en lingua castelá.

Baixo dela atópanse os seus compoñentes. Ningunha destas categorías dan lugar a frases válidas só a categoría superior.

Ao finalizar toda a xerarquía chegamos ás palabras que son as unidades mínimas con significado que pode adoptar unha frase.

Aplicando as xerarquía e substituíndo elementos, chegamos ao momento onde todas as categorías sintácticas convertéronse en palabras, obtendo xa que logo unha oración VALIDA. (Por exemplo: O neno corre). Este proceso chámase produción ou xeración.

En resumo:

[editar] Elementos constituíntes

Unha gramática formal é un modelo matemático composto por unha serie de categorías sintácticas que se combinan entre si por medio dunhas regras sintácticas que definen como se crea unha categoría sintáctica por medio doutras ou símbolos da gramática.
Existe unha única categoría superior que denota cadeas completas e válidas.

[editar] Mecanismos de Especificación

Por medio destes elementos constituíntes defínese un mecanismo de especificación consistente en repetir o mecanismo de substitución dunha categoría polos seus constituíntes en función das regras comezando pola categoría superior e finalizando cando a oración xa non contén ningunha categoría.

Desta forma, a gramática pode xerar ou producir cada unha das cadeas da linguaxe correspondente e só estas cadeas.

[editar] Definición

Unha Gramática Formal é unha cuádrupla $G = (N, T, P, S) \,$ onde:

$N$ é un alfabeto de símbolos non terminais (variables).
$T$ é un alfabeto de símbolos terminais (constantes).
Debe cumprirse que $N \cap T = \emptyset$ . denotaremos con $\Sigma = N \cup T$ o alfabeto da gramática.
$S \in N$ é o símbolo inicial ou axioma da gramática.
$P \,$ é o conxunto de regras de produción, da forma $P = \,$ { α → β | α $\in \Sigma^* N \Sigma^*$ β $\in \Sigma^*$ }

É dicir, a cadea α debe conter polo menos unha variable, que pode estar rodeada dun contexto.

[editar] Derivacións

Sea $G = (N, T, P, S)$ una gramática, e sexan α, β, δ, φ, ρ, ... palabras de $Σ *$ . Entón

β derivase de α nun paso de derivación, e denotámolo con α $\Rightarrow$ β se existen dúas cadas $\phi_1, \phi_2 \in \Sigma^*$ , e unha producción δ → ρ tales que α = $φ 1$ δ $φ 2$ , e β = $φ 1$ ρ $φ 2$

Notamos con $\Rightarrow^*$ ó peche reflexivo e transitivo de $\Rightarrow$ . É dicir α $\Rightarrow^*$ β denota a unha secuenza de derivacións nun número arbitrario de pasos dende α hasta β.

$x \in \Sigma^*$ é unha forma sentencial de $G$ , pódese obter a seguinte secuencia de derivacións $S \Rightarrow^* x$ . No caso particular de que $x \in T^*$ dícese que x é unha sentenza