Gramática formal

Gramática formal

Una gramática formal es una estructura lógico matemática con un conjunto de reglas de formación que definen las cadenas de caracteres admisibles en un determinado lenguaje formal o lengua natural. Las gramáticas formales aparecen en varios contextos diferentes: la lógica matemática, las ciencias de la computación y la lingüística teórica, frecuentemente con métodos e intereses divergentes.

gramática ("G") desde el punto de vista de la teoría de autómatas es un conjunto finito de reglas que describen toda la secuencia de símbolos pertenecientes a un lenguaje específico L. Dos gramáticas que describan el mismo lenguaje se llaman gramáticas equivalentes.

Una gramática es una estructura algebraica formada por cuatro elementos fundamentales:

G = { NT, T, S, P }

donde

NT es el conjunto de elementos No Terminales

T es el conjunto de elementos Terminales

S es el Símbolo inicial de la gramática

P es el conjunto de Reglas de Producción

Ejemplo 1:

Consideremos la gramática: G = (V, Σ, Q0, P), donde

V := {Q0}, Σ := {a, b}, , P := {(Q0, aQ0),(Q0, λ)}.

El sistema de transición tiene por configuraciones

S := {Q0, a, b}

∗ y un ejemplo de una computación sería:

aaQ0bb → aaaQ0bb → aaaaQ0bb → aaaaλbb = aaaabb.

Nótese que las dos primeras veces hemos usado la regla de reescritura (Q0, aQ0) y la última vez hemos usado (Q0, λ).

Ejemplo 2:

Consideremos la gramática: G = (V, Σ, Q0, P), donde

V := {Q0}, Σ := {a, b}, , P := {Q0 7→ aAb, aA 7→ aaAb|λ}.

Un ejemplo de una computación sería:

Q0 7→ aAb 7→ aaAb 7→ aab.

Curiosamente, el lenguaje especificado también puede ser especificado por esta otra gramática:

V := {Q0}, Σ := {a, b}, , P := {Q0 7→ b|aA, A 7→ aA|b}.

                        

Ejemplo 3:

La gramática que genera el lenguaje

L = {λ, a, aa, aaa, . . .}

se puede describir de la siguiente manera

V = {hQi}, Σ = {a, b},

donde las producciones serían:

hQi = ahQi

hQi = λ.