Gramáticas

Gramáticas Regulares
Elena Gaudioso Vázquez y Tomás García Saiz

Introducción
La descripción de un lenguaje en base a gramáticas es importante ya que
permite analizar la estructura gramatical del lenguaje.
La descripción de una gramática se basa en los siguientes cuatro elementos:
Un conjunto finito de símbolos que forman las cadenas del lenguaje. Estos
símbolos se denominan símbolosterminales y al conjunto que los agrupa
Alfabeto de símbolos terminales.
Un conjunto finito de símbolos denominados símbolos no terminales que
actuan a modo de variables. Cada símbolo no terminal representa un
conjunto de cadenas que se derivan a partir de ese símbolo no terminal.
Un símbolo inicial, que será un símbolo contenido en el conjunto de
símbolos no terminales y a partir del cual secomienzan a realizar las
derivaciones de la gramática.
Un conjunto finito de producciones o reglas de reescritura que representan
la definición recursiva de un lenguaje.
De manera informal se puede decir que derivar una gramática consiste en
ir substituyendo los símbolos no terminales por el lado derecho de la regla de
reescritura en la que dichos símbolos no terminales aparecen en el ladoizquierdo.
Cualquier derivación de una gramática se inicia con la derivación del símbolo
inicial.
A modo de ejemplo inicial consideremos la siguiente gramática, con símbolo
inicial S:
S → xA
S → yB
A → xA
A→x
B → yB
B→y
Una posible derivación de la gramática sería la siguiente:
A→xA
A→x
S → xA =⇒ S → xxA =⇒ S → xxx
Esta derivación generaría la cadena xxx.
Otra posible derivación podríaser la siguiente:
B→yB
B→y
S → yB =⇒ S → yyB =⇒ S → yyy
que generaría la cadena yyy
1

Un tipo especial de producción es aquella cuyo lado derecho contiene el
símbolo λ. En este caso, se considera que esta producción deriva a vacío y no
genera ningún símbolo adicional. Así por ejemplo si consideramos la siguiente
gramática:
S → xA
A → xA
A→λ
una posible derivación sería:
A→xA
A→λS → xA =⇒ S → xxA =⇒ S → xx
El conjunto de cadenas que se pueden derivar de una determinada cadena
forman un lenguaje. Así, dada una gramática G, el lenguaje que genera se
representa mediante la notación L(G).
Dada una determinada gramática estructurada por frases, la propia estructura
de las reglas de reescritura o producciones determinará de qué tipo es dicha
gramática.
En el siguienteapartado profundizaremos en la estructura de las gramáticas
regulares.

Gramáticas Regulares
Las producciones de una gramática regular se ajustan a la siguiente estructura:
El lado izquierdo de las reglas de reescritura contienen un único símbolo no
terminal
El lado derecho de las reglas de reescritura contienen: un único símbolo
terminal, un símbolo terminal seguido de un símbolo noterminal, o el
símbolo λ
De acuerdo a estas condiciones, las gramáticas vistas en el apartado anterior
son gramáticas regulares.
Dada una gramática regular el lenguaje que genera es siempre un lenguaje
regular que puede representarse igualmente mediante un autómata finito o
mediante una expresión regular.
A continuación mostramos más ejemplos de gramáticas regulares:
La siguiente gramáticaregular:
S→λ
2

es una gramática regular que genera la cadena vacía
Dado el alfabeto Σ = {x, y}, la siguiente gramática regular:

S → xS
S → yS
S→λ

genera el lenguaje formado por todas las cadenas que se pueden formar con
el alfabeto Σ, esto es, Σ∗
Dado el alfabeto Σ = {x, y}, la siguiente gramática regular, con símbolo
inicial S:
S → xS
S → yS
A → yA
A → xA
A→λ

genera el lenguajevacío, esto es, L(G) = ∅
Dado el alfabeto Σ = {x, y}, la siguiente gramática regular, con símbolo
inicial S:
S → xA
A→y
A → xB
B→λ

genera el lenguaje formado únicamente por dos cadenas, L(G) = {xx, xy}
Puesto que las gramáticas regulares y los autómatas finitos reconocen ambos
los lenguajes regulares, en la siguiente sección vamos a comprobar cómo, dada
una gramática regular, se...