las gramáticas cuyas reglas son de la forma A → aB o bien A → a, donde A y B son variables, y a es un caracter terminal. A estas gramáticas se les llama regulares.
Ejemplo.- Sea una gramática con las siguientes reglas:
1. S → aA
2. S → bA
3. A → aB
4. A → bB
5. A → a
6. B → aA
7. B → bA
La idea para aplicar una gramática es que se parte de una variable, llamada símbolo inicial, y se aplican repetidamente las reglas gramaticales, hasta que ya no haya variables en la palabra. En ese momento se dice que la palabra resultante es generada por la gramática, o en forma equivalente, que la palabra resultante es parte del lenguaje de esa gramática.
Por ejemplo, en la gramática que acabamos de presentar, si consideramos que las variables son S (que será el símbolo inicial), A y B, y las constantes a y b, partiendo de S podemos producir bA (por la segunda regla), luego de bA podemos pasar a ba (por la quinta regla).
Como ba tiene sólo constantes, podemos concluir que la palabra ba es parte del lenguaje generado por la gramática dada. De hecho el lenguaje generado por esta gramática es el de las palabras en {a, b} de longitud par terminadas en a.
Definición.- Una gramática regular es un cuádruplo (V,
∑ ,R, S) en donde:
V es un alfabeto de variables,
∑ es un alfabeto de constantes,
R, el conjunto de reglas, es un subconjunto finito de V × (
∑ V U ∑ ).
S, el símbolo inicial, es un elemento de V .
Por ejemplo, la gramática que presentamos arriba se representaría formalmente como:
({S, A,B}, {a, b}, {(S, aA), (S, bA), (A, aB), (A, bB), (A, a), (B, aA), (B, bA)}, S)
Usualmente las reglas no se escriben como pares ordenados (A, aB), como lo requeriría la definición anterior, sino como A → aB; esto es simplemente cuestión de facilidad de notación. La aplicación de una gramática se formaliza con las siguientes nociones:
- Una cadena uXv deriva en un paso una cadena u v, escrito como uXv ) u v, si hay una regla X α €R en la gramática.
- Una cadena w € ∑* (esto es, formada exclusivamente por constantes) es derivable a partir de una gramática G si existe una secuencia de pasos de derivación S => α1=> α2=> …=> w
A una secuencia de pasos de derivación le llamamos simplemente derivación. Dicho de otra manera, una palabra
w € ∑* es derivable a partir de G ssi S =>* w, donde =>* denota la cerradura reflexiva y transitiva de =>.
Definición.- El lenguaje generado por una gramática G, L(G), es igual al conjunto de las palabras derivables a partir de su símbolo inicial.
Esto es, L(G) = {w € ∑* / S =>* w}.
Frecuentemente es fácil mostrar que una palabra dada w es derivable a partir del símbolo inicial S; por ejemplo, en la gramática presentada arriba, se puede mostrar que S => . . .=> bababa (esto es, que la palabra bababa puede ser derivada a partir del símbolo inicial S, por lo que bababa € L(G).
Ejemplo.- Proponer una gramática que genere el lenguaje de las palabras en {a, b} que contienen la subcadena bb, como abb, ababba, etc.
Vamos a utilizar las variables de una manera similar a como se utilizaban en los AF los estados, esto es, como memorias para “recordar” situaciones. As´ı tendremos las siguientes variables:
A, que recuerda que aún no se produce ninguna b.
B, que recuerda que se produjo una b.
C, que recuerda que ya se produjeron las dos b’s.
Ahora podemos proponer reglas, pregunt´andonos a qu´e situaci´on se llega al producir una a o b. Por ejemplo, a partir de A, si se produce una a se debe llegar a la misma A, pero si llega una b se llegará la variable B. Con estas ideas se proponen las siguientes reglas:
1. A → aA
2. A → bB
3. B → aA
4. B → bC
5. C → aC
6. C → bC
Finalmente, para terminar la producción de una palabra hecha solamente de constantes es necesaria al menos una regla que no produzca variables en su lado derecho. Tal regla no se encuentra aún en la gramática dada. Como las palabras correctas tienen bb, pensamos que una regla adicional podría ser C →a y también C →b. En efecto, con tales reglas podemos producir, por ejemplo, la palabra abba, mediante la derivación siguiente:
A => aA => abB => abbC => abba
Sin embargo, tambi´en podemos verificar que la palabra abb, que pertenece al lenguaje, no puede producirse con las reglas dadas. Hace falta aún otra regla, B → b, con la que se completa nuestra gramática.
Al diseñar gramáticas regulares, podemos incurrir en los mismos errores que en los AF, es decir, que sean incorrectas (producen palabras que no deberían) o bien incompletas (no pueden generar palabras que pertenecen al lenguaje), o bien ambas cosas a la vez. No vamos a examinar métodos particulares de diseño de gramáticas regulares; en vez de ello mejor vamos a examinar métodos por los que es muy simple convertir las gramáticas regulares a AF y viceversa.
Este obra está bajo una
licencia de Creative Commons Reconocimiento-CompartirIgual 3.0 Unported.
Entradas
