Gramáticas Regulares

Publicado: octubre 27, 2010 en Sin categoría

Gramáticas  Regulares

Gramática: La gramática es un ente formal para especificar, de una manera finita, el conjunto  de símbolos que constituye un lenguaje, así  tenemos la gramática del español, del francés, etc.

Las reglas de las gramáticas regulares son de la forma A→ aB o bien A→A, donde A y B son variables, y a es un carácter terminal. A estas gramáticas se les llama regulares.

Ejemplo.- Sea una gramática con las siguientes reglas.

S→Aa

s→bA

A→aB

A→bB

A→a

b→aA

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. E n 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

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 x (Є V U Є)

S, el símbolo inicial, es un elemento de V .

Por ejemplo, la gramática que presentamos arriba se representara 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á la definición anterior, sino como A→ aB; esto es simplemente cuestión de facilidad de notación.

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ándonos a qué situación 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 llegara a la variable B. Con estas ideas se proponen las siguientes reglas:

A→aA

A→bB

B→aA

B→bC

C→aC

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 aun en la gramática dada. Como las palabras correctas tienen bb, pensamos que una regla adicional podrá 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én podemos verificar que la palabra abb, que pertenece al lenguaje, no puede producirse con las reglas dadas. Hace falta aun 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án) 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.

 

Autómatas finitos y gramáticas regulares.

De manera similar a como hicimos en la sección anterior, aquí vamos a establecer la equivalencia entre las gramáticas regulares y los lenguajes regulares -y por ende los autómatas finitos. Este resultado es establecido por el siguiente

Teorema.- La clase de los lenguajes generados por alguna gramática regular es exactamente la de los lenguajes regulares.

La prueba de este teorema consiste en proponer un procedimiento para, a partir de una gramática dada, construir un autómata finito, y viceversa.

Dicho procedimiento es directo, y consiste en asociar a los símbolos no terminales de la gramática (las variables) los estados de un autómata. Así, para cada regla   A → bC en la gramática tenemos una transición (A, b,C) en el autómata.

Sin embargo, queda pendiente el caso de las reglas A → b Para estos casos, se tienen transiciones (A, b,Z), donde Z es un nuevo estado para el que no hay un no terminal asociado; Z es el único estado final del autómata.

Ejemplo.- Obtener un autómata finito para la gramática regular G siguiente

S→aA

S→bA

A→aB

A→bB

A→a

B→aA

Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivs 2.5 Generic License.

About these ads

Deja un comentario

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s