3_Lenguajes_gramaticas_y_ER - Fernando Cesar Sandoval Padilla

Vista previa del material en texto

33 
 
LENGUAJES, 
GRAMÁTICAS 
Y 
EXPRESIONES 
REGULARES 
 
 
34 
 
Lenguajes y gramáticas regulares 
Los lenguajes que generan este tipo de gramáticas se conocen como Lenguajes Regulares 
y son especialmente adecuados para representar las características léxicas de un lenguaje 
de programación. 
Este tipo de gramáticas contiene restricciones tanto de la parte derecha como de la parte 
izquierda de las producciones. Existen dos tipos de gramáticas regulares: gramáticas 
lineales por la derecha y gramáticas lineales por la izquierda. Sus producciones están 
dadas por: 
 
1. Gramáticas lineales por la derecha (GLD): 
A ::= a, A ::= aV, S ::= λ 
dónde A,V,S ∈ ΣN, a ∈ ΣT y S es el símbolo inicial de la gramática 
 
2. Gramáticas lineales por la izquierda (GLI): 
A ::= a, A ::= Va, S ::= λ 
dónde A,V,S ∈ ΣN, a ∈ ΣT y S es el símbolo inicial de la gramática 
 
Ejemplo: 
Supongamos que Σ={a,b,...,z} 
 
El lenguaje L1 = {an | n ≥ 0} ó L1 = { λ,a,aa,aaa,…..} puede ser generado por la gramática 
lineal por la izquierda: 
S::= λ| Sa 
 
Y por la gramática lineal por la derecha: 
S::= λ| aS 
 
El lenguaje de todas las palabras que empiezan con a puede ser generado por la gramática 
lineal por la izquierda: 
S::=a|Sa|Sb|Sc|….|Sz 
Y por la gramática lineal por la derecha: 
S::=aA, A::=aA|bA|…|zA|a|b|c|…|z 
 
Dado un lenguaje regular, existe al menos una gramática lineal por la izquierda y una 
gramática lineal por la derecha que lo generan. 
 
Es importante mencionar que en una gramática tipo 3 no puede existir combinación de 
reglas lineales por la derecha y lineales por la izquierda, si esto sucede la gramática es tipo 
2. 
 
Ejemplo: 
Considere la siguiente gramática, que contiene reglas lineales por la derecha y lineales por 
la izquierda: 
 
 
35 
 
S::=aB|λ, B::=Sb|b 
Podría pensarse que es una gramática regular o tipo 3, sin embargo esta gramática genera 
el lenguaje L = {anbn | n ≥ 0} que es un lenguaje libre de contexto o tipo 2 y sólo puede ser 
generado por gramáticas tipo 2, 1 o 0. Por lo que, al combinar reglas lineales por la 
izquierda y lineales por la derecha la gramática se convierte en tipo 2. 
Cómo diseñar gramáticas regulares? 
El diseño y construcción de gramáticas es una cuestión de práctica y creatividad. En 
general construir gramáticas es más difícil que construir autómatas, ya que estamos 
acostumbrados a programar máquinas que realicen tareas específicas más que diseñar 
una gramática. A continuación se presentan algunas sugerencias para hacer más simple la 
construcción de gramáticas regulares. 
1. Antes de construir cualquier gramática primero hay que entender el lenguaje que 
ésta generará, es decir, determinar cuáles palabras pertenecen al lenguaje y cuáles 
no, cómo son esas palabras, con que letra comienzan, con cuál terminan, que 
llevan en medio, etc. 
2. Debido a la forma que tienen las reglas de tipo 3, hay que ver las gramáticas 
regulares como una serie de pasos, en donde cada uno de ellos concatena una 
letra a la palabra (ya sea a la izquierda o a la derecha), y después manda llamar a la 
siguiente regla (o paso). 
3. En el caso de gramáticas lineales por la derecha, tenemos que analizar las palabras 
del lenguaje para determinar con qué letras comienzan dichas palabras, es decir, si 
todas las palabras comienzan con “c” entonces mi primer regla deberá tener un 
símbolo terminal “c”, y el símbolo no terminal será la regla siguiente que le 
concatenará letras a la “c” que ya se tiene. 
Ejemplo: Sea el lenguaje L={ c{a,b}n | n > 0} 
a) Las palabras que pertenecen a este lenguaje son {ca,cb,caa,cab,cba,cbb,caaa, 
caab, caba, …} 
b) Analizando las palabras de izquierda a derecha, se puede ver que todas 
comienzan con “c” y después pueden tener cualquier combinación de a’s o b’s. 
c) Para diseñar la gramática primero debemos tener una regla que nos genere la 
primer letra de las palabras y mande llamar otra regla que concatenará las 
siguientes letras. En este caso la regla S -> cA, pone una “c” al inicio y manda 
llamar a la regla “A” que será la regla que genere las combinaciones de a’s y 
b’s. 
d) Se deberán diseñar las reglas A->a, A->b para que se puedan generar las 
palabras “ca”, “cb”. Así mismo, se deben generar las reglas recursivas A->aA, 
 
 
36 
 
A->bA que nos permiten, junto con las reglas anteriores, hacer combinaciones 
de cualquier cantidad de a’s y b’s. 
4. En el caso de gramáticas lineales por la izquierda, el proceso es muy similar al 
anterior pero se tienen que analizar las palabras de derecha a izquierda y diseñar 
primero las reglas que concatenen las letras con las que terminan las palabras y 
después diseñar las reglas que van concatenando letras en medio y después las 
letras del principio. 
Expresiones regulares 
Es una notación normalizada para representar lenguajes regulares. 
 
Definición formal 
Una expresión regular (ER) se puede definir de acuerdo a los siguientes criterios: 
 
 Ø es una ER que representa al lenguaje vacío (no tiene palabras) LØ = Ø 
 λ es una ER que representa al lenguaje Lλ = {λ} 
 a ∈ Σ es una ER que representa al lenguaje La = {a} 
 Si a y b son ER entonces a + b también lo es y representa al lenguaje La+b = La ∪ Lb 
 Si a y b son ER entonces ab también lo es y representa al lenguaje Lab= LaLb 
 Si a es una ER entonces a* también lo es y representa al lenguaje 
a∗ = ⋃ La
i
∞
i=0
 
 
La prioridad de las operaciones, que puede modificarse utilizando paréntesis, es de mayor 
a menor: *, · ,+ 
 
Ejemplo: 
Sea Σ={ 0,1 } 
1. 01 + 001 es una ER que representa al lenguaje L = {01,001} 
2. 0*10* es una ER que representa a cualquier cadena binaria en la que existe un solo 
1, es decir, L={ 0n10m | n,m ≥ 0} 
3. Expresión regular que genere secuencias de 1 y 0 alternados. 
(01)* + (10)* + 0(10)* + 1(01)* ó (λ + 1)(01)*( λ + 0) 
Sea Σ={ a,b,c } 
1. a(a+b+c)* representa a cualquier cadena que empieza con a 
2. (a+b+c)* representa al lenguaje universal definido sobre el alfabeto 
 
Propiedades de la unión de expresiones regulares (+,U) 
 Asociativa: (a+b)+c = a+(b+c) 
 Conmutativa: a+b = b+a 
 Elemento neutro (Ø): a+Ø = a 
 
 
37 
 
 Idempotencia: a+a = a 
 
Propiedades de la concatenación de expresiones regulares (·) 
 Asociativa: (ab)c = a(bc) 
 Distributiva respecto de la unión: a(b+c)=ab+ac 
 Elemento neutro (λ): aλ = λa =a 
 aØ = Ø 
 No es conmutativa 
 
Propiedades del cierre de Kleene de expresiones regulares (*) 
 λ * = λ 
 Ø* = λ 
 a*a* = a* 
 a*a = aa* , por simplicidad: a+ 
 (a*)* = α* 
 a* = λ+aa* = λ+a+