Lenguajes Formales y Gramáticas

Programación II

Margarita Álvarez

Características de las Gramáticas de Estructura de Frase  

Gramáticas de contexto sensitivo  Recursividad Gramáticas libres de contexto  Árbol de derivación  Derivación más a la izquierda y más a la derecha  Ambigüedad  Factorización a izquierda  Gramáticas propias    





Gramáticas sin ciclos (recursividad a izquierda directa e indirecta) Vacuidad del lenguaje Símbolos Inútiles Reglas lambda Reglas Unitarias

Expresiones Regulares

Recursividad en las Gramáticas de Contexto Sensitivo Se dice que una gramática G es recursiva si existe un algoritmo que determina para cualquier palabra no vacía w, si w es generada por G. Teorema: Si G = (VN, VT, S , P) es una gramática sensible al contexto entonces G es recursiva. Demostración: Sea w un elemento de VT* de longitud n > 0. Definimos Tm como el conjunto de cadenas no vacías  de VN  VT de longitud a lo sumo n tales que: * S   por una derivación a lo sumo de m pasos. Puede verse que: T0 = {S} y que Tm = Tm-1  {  / ||  n y existe  en Tm-1 :   }

Recursividad en las Gramáticas de Contexto Sensitivo *

Se observa que si S   y ||  n entonces  debe estar en Tm para algún m.  Si || > n o si no deriva de S, entonces  no estará en ningún Tm.  Como Tm depende solo de Tm-1 , si para un m es Tm = Tm-1, también se dará la igualdad para las siguientes.  El algoritmo consiste en calcular recursivamente T1, T2, T3,… hasta que se obtenga Tm = Tm-1 . Si w no está en Tm entonces w no estará en L(G).  Probemos que efectivamente existe tal m. Como VNVT es finito, el número de cadenas  de longitud  n también. Como la sucesión T1,T2,... es creciente debe estabilizarse. 

Ejemplo - Recursividad en las Gramáticas de Contexto Sensitivo Ejemplo Determinar si w = aabb está en L(G). G = {S,A,B}, {a,b}, P ,S} donde P es: (1) (2) (3) (4)

S  aB S  bA A a A  aS

(5) (6) (7) (8)

A  bAA Bb B  bS B  aBB

Aplicando el algoritmo:  T0 = {S}  T1 = {S, aB, bA}  T2 = {S, aB, bA, ab, abS, aaBB, ba, baS, bbAA}  T3 = {S, aB, bA, ab, abS, aaBB, ba, baS, bbAA, abbA, abaB,aabB,bbAa, aaBb, baaB,babA,bbaA}  T4 = {S, aB, bA, ab, abS, aaBB, ba, baS, bbAA, abbA, abaB,aabB,bbAa, aaBb, baaB,babA,bbaA,bbAa,abba,abab,aabb,baab,baba,bbaa}  T 4 = T5  w está en T4, entonces w  L(G).

Ejemplo - Recursividad en las Gramáticas de Contexto Sensitivo Ejemplo Determinar si w = abac está en L(G). G = {S,B,C,D}, {a,b,c}, P ,S} donde P es: (1) (2) (3) (4)

S  aSBC S  aBC CB  DB DB  DC

Aplicando el algoritmo:  T0 = {S}  T1 = {S, aSBC,aBC}  T2 = {S, aSBC,aBC,abC}  T3 = {S, aSBC,aBC,abC,abc}  T3 = T4  w no está en T3, entonces w  L(G).

(5) (6) (7) (8) (9)

DC  BC aB  ab bB  bb bC  bc cC  cc

Observar que también aaSBCBC y aaBCBC pueden derivarse de aSBC por producciones (1) y (2), ellas no están en T2 debido a que sus longitudes son mayores que 4 y |w| = |abac| = 4.

Árbol de Derivación Sea G = (VN, VT , S , P) una gramática libre de contexto, un árbol es un árbol de derivación para G si: La

raíz está etiquetada con el símbolo inicial S. Cada hoja está etiquetada con un símbolo terminal o con . Si A es un no terminal que etiqueta a algún nodo intermedio y X1 , X2 , ... , Xk son las etiquetas de los hijos de ese nodo, de izquierda a derecha, entonces: A  X1 X2 ... Xk es una producción en P. Aquí, X1, X2,..., Xk son símbolos terminales y/o no terminales. Si A , entonces el nodo etiquetado con A tiene sólo un hijo etiquetado con .

Árbol de Derivación La derivación empieza con el símbolo distinguido S. A continuación se colocan tantas ramas como símbolos terminales y no terminales hayan concatenados en el lado derecho de la regla de producción. Se van sustituyendo cada no terminal por alguna de las partes derechas de una de sus reglas hasta llegar a obtener una sentencia o hilera. Ejemplo: Determinar si w = aabbaa está en L(G). G = {S,A}, {a,b}, P ,S} donde P es: S  aAS / a A  SbA / SS / ba

Para x = aabbaa se tiene: S a

A S

S b A

Propiedad: Sea G = (VN, VT, S, P) una gramática de contexto a libre. Entonces S * , si y sólo si, hay un árbol de derivación en la gramática G con resultado .

b

a a

Derivación más a la Izquierda y más a la Derecha 





Si en cada paso de un proceso de derivación se sustituye (o se aplica) a la variable de más a la izquierda por alguna de sus partes derecha de las reglas de producción se dice que es una derivación izquierda. De una forma análoga se define la derivación derecha si las sustituciones que se van realizando en cada regla son siempre en la variable de más a la derecha. Ambas derivaciones se indican con el símbolo de derivación directa  colocando encima una I (izquierda) o una D (derecha) según corresponda. Se pueden tener también los cierres transitivos y reflexivos con estas nuevas derivaciones.

Ejemplo - Derivación más a la Izquierda y

más a la Derecha Ejemplo: Realizar la derivación más I I I I I a la izquierda y más a la derecha para A  BF  ECF  aCF  abF  abc w = abc. D D D D D G = ({A,B,C,E,F}, {a,b,c},P,A) donde P es: A  BF Cb B  EC Fc Ea

A  BF  Bc  ECc  Ebc  abc

I I I I Ejemplo: Realizar la derivación más a la izquierda y más a la derecha para S  aASI  aSbAS  aabAS  w = aabbaa. aabbaS  aabbaa

G = ({S,A}, {a,b},P,A) donde P es: S  aAS / a A  SbA/ SS / ba

D

D

D

D

S  aAS  aAa  aSbAa  aSbbaa D

 aabbaa

Ambigüedad 







Se dice que una gramática es ambigua si el lenguaje tiene alguna hilera que tenga más de un árbol sintáctico o más de una derivación más a la izquierda o más de una derivación más a la derecha. Se llama ambigua a la gramática y no al lenguaje que define, puesto que frecuentemente se puede modificar la gramática para que deje de ser ambigua. Sin embargo, hay lenguajes para los cuales existen únicamente gramáticas ambiguas, a estos lenguajes se los denomina intrínsecamente ambiguos. La ambigüedad de una gramática es una propiedad indecidible, es decir, no existe ningún algoritmo que acepte una gramática y determine con certeza y en un tiempo finito si la gramática es ambigua o no.

Ejemplo - Ambigüedad Ejemplo Determinar si la siguiente gramática es ambigua. Sea G = ({S}, {a,+,*,(,)}, P, S} donde P es: S  a / S+S / S*S / (S) S

S S

S + S a

*

S

Hay dos árboles de derivación para la hilera a+a*a luego la gramática es ambigua. Se modifica la gramática para que deje de ser ambigua: G = ({S,T,E}, {a,+,*,(,)}, P, S}

S * S

S + S

a

a

a

a

a

SS+T/T TT*F/F F  (S) / a

Factorización a Izquierda 



Si A 1/2 son dos producciones de A y la entrada comienza con una cadena no vacía , no se sabe si expandir A a 1 ó a 2. Sin embargo, se puede retrasar la decisión expandiendo A a A'. Entonces, después de ver la entrada derivada de , se puede expandir A' a 1 ó a 2. Es decir, factorizadas por izquierda las producciones originales se convierten en: A  A' A'  1 / 2

Ejemplo Dada la siguiente gramática factorizar por izquierda. Sea G = ({P,E}, {i,t,e,a,b}, P, P} donde P es: P  iEtP / iEtPeP / a Eb La gramática resultante es: G = ({P,P´,E}, {i,t,e,a,b}, P, P} donde P es: P  iEtPP' / a P'  eP /  Eb

Recursividad a Izquierda Directa Es recursiva a izquierda si las reglas de producción son de la forma: A  A Algoritmo de supresión de la recursividad a izquierda: 1. Se toman las reglas del no terminal A que sea recursiva por izquierda de la forma: A  A 1 / A 2 / .... / A p / 1 / 2 /.../ q donde las primeras p alternativas son recursivas y las q restantes no lo son. 2. Se añade a la gramática un nuevo no terminal A' y todas las reglas A anteriores se sustituyen por las siguientes: A  i A  iA' 1iq A'  j A'  j A' 1jp Ejemplo Eliminar la recursividad a izquierda directa de la siguiente gramática: G = ({S}, {a, b}, P, S) donde P es: S  Sa / Sb / ab A  A1/A2 / 1 La gramática resultante es: G = ({S, S' }, {a, b}, P, S) donde P es: S  ab / abS' S'  a / b / aS' / bS'

Recursividad a Izquierda Indirecta Es recursiva a izquierda indirectamente si las reglas de producción son de la forma: A  B 1 / ... B  A 2 / … Algoritmo para suprimir la recursividad izquierda indirecta: • Se toma cada grupo de reglas de la forma: A  B 1 / B 2 / .../ B n /1 /.../ p B  A 1 / A 2 /.../A q / 1 / ... /  r • Se reemplaza A por la parte derecha de sus reglas quedando: B  B i j / k j / 1 / ... / r para cada i, j = 1, ... ,q con i = 1, ... ,n, y para cada k, j=1, ... ,q con k = 1, ... ,p • Luego se elimina la recursividad a izquierda directa.

Recursividad a Izquierda Indirecta Ejemplo: Eliminar la recursividad indirecta en la siguiente gramática: G = ({S, A}, {a, b, c}, P, S) donde P es: S  Aa / b A  Ac / Sb / c Se elimina la recursividad a izquierda indirecta. La gramática resultante es: G = ({S, A}, {a,b,c}, P, S) donde P es: S  Aa / b A  Ac / Aab / bb / c

Se elimina la recursividad a izquierda directa, quedando la gramática así: G = ({S, A. A' } ,{ a,b,c}, P, S) donde P es: S  Aa / b A  bb / c / bbA' / cA' A'  c / ab / cA' / abA'

Simplificación de Gramáticas 



Es muy importante que una gramática tenga sus reglas con un formato adecuado, lo que facilitará no sólo su lectura y comprensión sino también su compilación. Se pueden tener reglas que produzcan símbolos que no se usen después, o que produzcan la hilera nula, o bien que la regla acabe produciendo o llegando a la misma metanoción en que comenzó; estos son algunos ejemplos de casos que deben evitarse. También es muy conveniente que las gramáticas que se empleen no sean ambiguas. Toda gramática con imperfecciones se las puede transformar para convertirlas en otra gramática carente de imperfecciones.

Vacuidad del Lenguaje Un lenguaje vacío es aquel que no tiene hileras (ni siquiera la hilera nula), es decir, L(G) = . Algoritmo para determinar si una gramática genera un lenguaje vacío o no. begin VI = ; N = {A/ (A  t) de P y t  VT*} while N  VI do begin VI = N; N = VI  { B/(B ) de P y  (VTVI)*} end; if S  N then VACIO = "no" else VACIO = "si" end

Ejemplo G = ({S,A,B,C},{a}, P,S) donde P es: S  AB Ca Se aplica el algoritmo: VI

N



{C}

{C}

{C}

Vacío = "si "

Supresión de Símbolos Inútiles G = ({S,A,B,C},{a,,b,c}, P, S)

P es: Sea una gramática G = (VN, VT, S, P) , un símbolo X S  aAAA A  aAb / aC es útil, si se tiene las dos cadenas de derivaciones: B  Dc /Ac Cb * * S  X  t , sino X es inútil. Donde:  y   (VN VT)*, S VN, t VT y X (VN VT)

Se deben considerar dos aspectos para determinar la utilidad de un símbolo:  Se debe poder derivar alguna hilera del símbolo X, si es así se dice que X es terminable. 

X debe aparecer en alguna forma sentencial del axioma S, se le denomina entonces accesible.

Supresión de Símbolos Inútiles Algoritmo: para G = (VN, VT, P, S) y L(G), hallar G'=(V'N, VT, P', S) tal que para cualquier A de V'N se tiene alguna t VT*. begin VI = ; N = {A/ (A  t) de P y t  VT*} while N  VI do begin VI = N; N = VI  { B/(B ) de P y  (VTVI)*} end; VN' = N; end Para obtener G' se procede: • Se incluyen en V'N todos los no terminales A que tengan las reglas A  t. • Si se tiene la regla A  X1 X2 ... Xn, y cada Xi es un terminal o un no terminal que ya está en V'N, entonces la regla anterior puede producir una hilera terminal t con lo que A pertenece a V'N.

Ejemplo - Supresión de Símbolos Inútiles G = ({S,A,B,C,D},{a,,b,c}, P, S) donde P es: S  aAAA A  aAb / aC B  BD / Ac Cb Se aplica el algoritmo:

VI

N



{C}

{C}

{C,A}

{C,A}

{C,A,S,B}

{C,A,S,B}

{C,A,S,B}

El no terminal D no es terminable. Gramática Resultante G = ({S,A,B,C},{a,b,c}, P, S) donde P es: S  aAAA A  aAb / aC B  Ac Cb

Supresión de Símbolos Inútiles Algoritmo: dada una gramática G (la resultante de la anterior) hallar otra G' tal que para cualquier símbolo X de V'N  V'T existe un  y  de (V'N  V'T )* y: * SX begin VI = {S}; N = VI  {X/ (S   X  ) de P} while VI  N do begin VI = N; N = VI  {Y / A   Y  de P y A está en VI} end; V'N = N  VN; V'T = N  VT; P' es el nuevo conjunto de reglas cuyos símbolos están en V'N y V'T. end;

Ejemplo - Supresión de Símbolos Inútiles G = ({S,A,B,C},{a,b,c}, P, S) donde P es: S  aAAA A  aAb / aC B  Ac Cb Se aplica el algoritmo: VI

N

{S}

{S,a,A}

{S,a,A}

{S,a,A.b,C}

{S,a,A.b,C}

{S,a,A.b,C}

Gramática Resultante G = ({S,A,C},{a,b}, P, S) S --> aAAA A --> aAb / aC C --> b

Reglas Lambda Se llama regla lambda o borradora a una regla del tipo A . Un no terminal A se dice que es anulable si: * A Si  pertenece a L(G), entonces no se podrá eliminar todas las reglas  de la gramática, pero si no es así se puede eliminar. Se dice que una gramática es sin reglas, si se cumple una de las dos condiciones siguientes:

1) no hay ninguna regla  en P; 2) hay sólo una regla asociada al axioma S   y además S no aparece en la parte derecha de ninguna regla de P.

Reglas Lambda Algoritmo para determinar los no terminales que deriven en . begin VI = ; N = {A/ (A   ) de P} while VI  N do begin VI = N; N = VI  {B / B   y todos los símbolos de  son anulables} end; end; Se forma el conjunto de reglas P' como sigue: Si A  X1 X2 ... Xn es una producción de P, entonces agregar la producción A  1  2 ... n a P' donde: a) Si Xi no es anulable, entonces  i = Xi b) Si Xi es anulable, entonces i es (una vez) Xi y la otra . c) No añadir la regla A  , que ocurriría si todos los i son . Si S es anulable, agregar un nuevo no terminal S´ y la regla de producción S´  / S, para que S´ no aparece en la parte derecha de ninguna regla de P.

Ejemplo - Reglas Lambda G = ({S, A, B}, {a, b}, P, S) donde P es: S  AB A  aAb /  B  Bb /  Se aplica el algoritmo: VI

N



{A,B}

{A,B}

{A,B,S}

{A,B,S}

{A,B,S}

Gramática Resultante G = ({S, S´, A, B},{a,b}, P, S´) S'  S /  S  AB / A / B A  aAb / ab B  Bb / b

Reglas Unitarias Se llama regla unitaria a la que tiene el formato A  B. Algoritmo: se parte de una gramática sin reglas lambda ni símbolos inútiles. Se determinan los conjuntos NA para cada A  VN tal que A B. begin VI = ; N =A while VI  N do begin VI = N N = VI  {C / (B  C) en P y B está en VI} end; NA = N end; El conjunto P' se construye como sigue: Si A  B y B   (y no es una regla unitaria) poner A   en P'.

Ejemplo - Reglas Unitarias G = ({E, T, F}, {a, +, *, (, )}, P, E) donde P es:

EE+T/T TT*F/F F  (E) / a Se obtiene los conjuntos como sigue: VI

N



{E}

{E}

{E,T}

{E,T}

{E,T,F}

{E,T,F}

{E,T,F}

NE = {E,T,F} VI

N



{F}

{F}

{F}

NF = {F}

VI

N



{T}

{T}

{T,F}

{T,F}

{T,F} NT = {T,F}

Gramática Resultante G = ({E, T, F}, {a, +, *, (, )}, P´, E) donde P´es: E  E + T / T * F / (E) / a T  T * F / (E) / a F  (E) / a

Característica de las gramáticas regulares Característica de las gramáticas regulares  Se denomina operaciones regulares a la unión, concatenación y clausura de la iteración.  Existe una interesante propiedad para los lenguajes de estructura de frase que se la puede expresar de la siguiente manera: toda clase de lenguaje Li (i=0,1,2,3) es cerrada sobre las operaciones regulares.  Los lenguajes de tipo 3, generados por gramáticas regulares, tienen otra caracterización importante: se puede definir un lenguaje comenzando con un número finito de palabras y aplicando operaciones regulares sobre ellas. Este método se conoce como expresiones regulares.

Expresiones regulares Una ER se construye a partir de ER más simples utilizando un conjunto de reglas definitorias. Cada ER r representa un lenguaje L(r). Las reglas de definición especifican cómo se forma L(r) combinando de varias maneras los lenguajes representados por las subexpresiones de r. Reglas que definen las ERs sobre un alfabeto finito V . 1)  es una ER que designa {}; es decir, el conjunto que contiene la cadena vacía. 2) Si a es un símbolo de V, entonces a es una ER que designa {a}; por ejemplo, el conjunto que contiene la cadena a. 3) Suponiendo que r y s sean ERs que representan los lenguajes L(r) y L(s), entonces, ( r ) / ( s ) es una ER que representa L( r ) U L( s ) ( r) ( s ) es una ER que representa L( r ) L( s ). ( r )* es una ER que representa (L( r ))*.

Expresiones regulares Ejemplos de expresiones regulares Las siguientes son expresiones regulares sobre el vocabulario V = {a,b}:  ER = a/b  {a,b}  ER= (a/b)(a/b)  {aa,ab,ba.bb}  ER= aa/ab/ba/bb  {aa,ab,ba.bb}  ER= a*  { , a, aa, aaa, .... }.  ER= (a/b)*  conjunto de todas las cadenas que contienen cero o más casos de una a o b, es decir, el conjunto de todas las cadenas de a y b.  ER= a/a*b  conjunto que contiene la cadena de a y todas las que se componen de cero o más a seguidas de una b.

Expresiones regulares Se pueden evitar los paréntesis innecesarios en las expresiones regulares si se adoptan las convenciones:

a) Es opcional el uso de "." para denotar la concatenación. b) * tiene precedencia más alta que la concatenación (.) y que la unión (/) y es asociativa a izquierda. c) la concatenación tiene precedencia más alta que (/) y es asociativa a izquierda. d) la unión tiene menor precedencia y es asociativa a izquierda. Ejemplo: ((0(1*))/0) se puede escribir como: 01*/0

Expresiones regulares ABREVIATURAS EN LA NOTACIÓN 1- Uno o más casos: El operador unitario postfijo + significa "uno o más casos de". Si r es una ER que designa al lenguaje L(r), entonces (r)+ es una ER que designa al lenguaje (L(r))+ . r* = r+ /  y r+ = rr* son dos identidades algebraicas. 2- Cero o un caso: El operador unitario postfijo ? significa "cero o un caso de" . La notación r? es una abreviatura de r /  . Si r es una ER, entonces (r)? es una ER que designa el lenguaje L(r) U {}. 3- Clases de caracteres: La notación [abc], donde a, b y c son símbolos del vocabulario, designa la ER a/b/c . Una clase abreviada de carácter como [a-z] designa la ER a/b/ ... /z. Ejemplo: la ER que designa un identificador, que está formado por una letra seguido de cero o más letras o dígitos es el siguiente: [a-zA-Z][a-zA-Z0-9]*

Expresiones regulares PROPIEDADES Y EQUIVALENCIAS Si dos ER r y s representan al mismo lenguaje, se dice que r y s son equivalentes y se escribe r = s. Por ejemplo, (a/b) = (b/a). AXIOMA

DESCRIPCIÓN

r/s = s/r

La unión ( / ) es conmutativa

r/(s/t) = (r/s)/t

La unión ( / ) es asociativa

(rs)t = r(st)

La concatenación es asociativa

r(s/t) = rs / rt r=r

(s/t)r = sr / tr r=r

La concatenación distribuye sobre la unión ( / )  es el elemento identidad para la concatenación

r* = (r /  )*

Relación entre * y 

r** = r*

* es idempotente

/r=r

r/=r

 es el elemento identidad para la unión ( / )

Expresiones regulares Equivalencias

1- * =  2- .r = r.  =  3- * =  4- r*.r* = r* 5- r*.r = r.r* 6- r* =  / r / r2 / ... / rn / rn+1 . r* 7- r* =  / r . r* (caso particular de la equivalencia anterior, para n = 0) 8- r* =  / rn-1 / rn. r* 9- (r* / s*)* = (r*.s*)* = (r / s)* 10- (r.s)*r = r(s.r)* 11- (r*.s)* r* = (r / s)* 12- (r* s)* = (r / s)* s /  13- (s r*)* = s( r / s)* / 

Expresiones regulares OBTENCIÓN DE UNA GRAMÁTICA REGULAR A PARTIR DE UNA ER DERIVADA DE UNA EXPRESIÓN REGULAR Se llama "derivada" de una expresión regular R respecto al símbolo a  V al conjunto de las colas de todas las palabras o hileras representadas por R cuya cabeza es a. Formalmente: Da (R) = { x / a.x  R } CÁLCULO DE DERIVADAS Se define a continuación recursivamente la derivada de una ER: 1- Da () =  2- Da () =  3- Da (a) =  4- Da (b) =  Ambos casos pueden unificarse definiendo 5- Da (R / S) = Da(R) / Da(S) (R) =  si   R 6- Da (R.S) = Da (R.S) = Da(R) . S / (R). Da(S) (R) =  si   R 7- Da (R*) = = Da(R).R*

Expresiones regulares Da (R.S) Se consideran dos casos:    R. Entonces, al concatenar R con S, todas las palabras de R.S comenzarán con una palabra de R. Luego las palabras de R.S cuya cabeza sea a, comenzarán con palabras de R cuya cabeza sea a. Por lo tanto, en la derivada de la concatenación aparecerán las colas de esas mismas palabras de R concatenadas con palabras de S. Da (R.S) = Da(R). S    R. Entonces, las cadenas de R.S que comiencen con a serán de dos clases: 



las de R que empiecen con a, concatenadas con palabras cualesquiera de S. o las de S que empiecen con a concatenadas por la izquierda con . Luego:

Da(R.S) = Da(R).S / Da(S) Ambos casos pueden unificarse definiendo: (R) =  si   R (R) =  si   R Con esta simbología, se puede ver: Da (R.S) = Da(R) . S / (R). Da(S) cualquiera sea el caso (  R o  R).

Expresiones regulares Da (R*) = = Da ( / R / R2 /... ) = Da () / Da (R) / Da(R2) /... =  / Da(R) /Da(RR)/ ... =  / Da(R) /Da(R).R / (R).Da(R) / ... = Da(R) /Da(R).R / Da(R) R2 / ... = Da(R).R*

Expresiones regulares MÉTODO PARA LA OBTENCIÓN DE UNA GRAMÁTICA REGULAR A PARTIR DE UNA ER La operación de "derivación" de una ER puede aplicarse reiteradamente respecto al mismo símbolo u otros diferentes. Se representa en general, Dab(R) = Db(Da(R)) Una vez calculadas las derivadas sucesivas distintas, si se cumple que: a) Da(R) = S , tal que S no es  ni , en la gramática generadora equivalente existirá una regla de la forma: R  aS b) Si, además,   Da(R), es decir (Da(R)) = , existirá en la gramática una regla de producción de la forma: Ra c) Si Da(R) = , quiere decir que no existe en la gramática una regla cuya parte izquierda sea R y cuya parte derecha contenga a. d) Si, además,   (R0), es decir  (R0) = , donde R0 es la ER de partida, existirá en la gramática una regla de producción de la forma: R0  