TeoComp B2011: Gramaticas Regulares

Gramáticas regulares, GR,  lineales y por derecha.

Sea GR = (V,T,P,S) en donde:

V: son las variables o símbolos no terminales.
T: son los símbolos terminales, tal que T interceptado con V  es vacío.
P: es un subconjunto en Vx(T^*V unido con T) de reglas con la forma p --> q, en donde p pertenece a V y q a T^*V unido con T.
S: es un miembro de V escogido como símbolo inicial de la gramática.

Por ejemplo, para el lenguaje descrito por ER: (0+1)^*01(0+1)^* , la siguiente es una gramática regular:

s --> 0s.
s --> 1s.
s --> 01s'.
s' --> 0s'.
s' --> 1s'.
s' --> lambda.

Derivación GR: Dada una gramática regular como la anterior, una cadena av en la que a pertenece a T^* y v a V, se dice que ag en (T^*V Unión T^*) SE DERIVA DE av si existe una regla v --> g en P de forma que

con av y v --> g ==> ag

Teorema GR: Sea A un autómata finito. Entonces, existe una gramática regular, GR, tal que L(GR) = L(A).

Demostración: Supongamos que A = (Q, Sigma, delta, q_0, F) es tal que q_0 no pertenece a F. Construímos la gramática regular correspondiente así:

Sea V = Q. Sea T = Sigma. Sea S = q_0. Las producciones en P se obtienen así: Dada una variable q en Q:

q --> sp. ( con p en Q\F y s en Sigma ) es una producción si delta(q,s) = p

y dada q' en Q,

q --> s. (s en Sigma) es una producción si delta(q, s) pertenece a F. LQQD. 

Si el estado inicial q_0 pertenece a F, agregar las siguientes producciones a la gramática:

s --> q_0.

s --> lambda.