Clase9 - Gramática Regular

Vista previa del material en texto

ING. JORGE BUABUD
Lenguajes-Gramáticas Regulares 
y Autómatas Finitos. 
U.T.N. – F.R.T. 
S. y S. de los L. 
GRAMÁTICAS REGULARES (GR):
Recordemos: GR =  ΣN , ΣT , P , S 
✓ Las GR corresponden al Tipo 3 de la Jerarquía de Chomsky.
✓ Sus reglas pueden tener un formato regular por la derecha
N1 → wN2 o regular por la izquierda N1 → N2w, pero 
no ambos. También pueden tener reglas de la 
forma Ni → w. Donde Ni  N y w  T*
✓ Tienen la capacidad de generar solo Lenguajes Regulares.
✓ Sirven para describir el Nivel Lexicográfico de un Lenguaje.
✓ El modelo aceptor correspondiente es el Autómata Finito.
ING. JORGE BUABUD
U.T.N. – F.R.T. 
S. y S. de los L. 
GRAMÁTICAS REGULARES (GR):
Ejemplos de GR por Der
1) S → babaS | bb | A
A → bbB | a
B → bbaB | bA | 
2) S → bbbB | aaaA | C
A → aA | a
B → bB | aaC | 
C → bbB | 
Ejemplos de GR por Izq
3) S → Sbbaa | Aab | 
A → Aaaa | Bb | aa
B → A | Bbb
4) S → Cba | a
A → Baa | bbb | 
B → A | Cbb
C → Baa | Ab | 
Lenguajes-Gramáticas Regulares 
y Autómatas Finitos. 
ING. JORGE BUABUD
U.T.N. – F.R.T. 
S. y S. de los L. 
GRAMÁTICAS REGULARES (GR):
Forma Normal de Chomsky de tipo 3 o Regular (FNC3):
Reg. Der. Reg. Der. o Izq. 
Reg. Izq. donde NiN , tT 
Como excepción pueden tener la regla 
en cuyo caso S no debe aparecer en la parte derecha.
FORMATO ESTÁNDAR: 
Con el objetivo de facilitar el procesamiento de las reglas 
de producción, se definen estándares para cada tipo de 
gramática según la Jerarquía de Chomsky.
N1 → tN2
N1 → N2t
N1 → t
S → λ
Lenguajes-Gramáticas Regulares 
y Autómatas Finitos. 
ING. JORGE BUABUD
U.T.N. – F.R.T. 
S. y S. de los L. 
GRAMÁTICAS REGULARES (GR):
FNC3 GR por Derecha
1) S → bS | a | aA
A → bB | aA
B → bB | b
2) S → bB | aA | b | 
A → aA | a
B → bC | aC
C → bC | b
FNC3 GR por Izquierda
3) S → b | Aa | 
A → Aa | Bb | a
B → Bb | a
4) S → Cb | Aa
A → Ba | b
B → Aa | Sb
C → Ba | Ab | b
EJEMPLOS FORMA NORMAL DE CHOMSKY TIPO 3:
Lenguajes-Gramáticas Regulares 
y Autómatas Finitos. 
ING. JORGE BUABUD
U.T.N. – F.R.T. 
S. y S. de los L. 
GRAMÁTICAS REGULARES (GR):
1.- Eliminar reglas innecesarias.
2.- Eliminar el axioma S de la derecha, si es que   L(GR).
3.- Eliminar reglas de redenominación o renombrado: N1 → N2
4.- Eliminar reglas de borrado: N→ 
5.- Realizar las sustituciones necesarias para reducir a uno la 
longitud de las secuencias de terminales.
MÉTODO PARA OBTENER LA FNC3:
Lenguajes-Gramáticas Regulares 
y Autómatas Finitos. 
ING. JORGE BUABUD
U.T.N. – F.R.T. 
S. y S. de los L. 
GRAMÁTICAS REGULARES (GR):
1.- Eliminar reglas innecesarias: Son producciones que no aportan nada.
1.1.- Reglas que tienen no-terminales inútiles, es decir aquellos N que 
NO cumplen con: o 
y donde S es el axioma, w  T* 
1.2.- Reglas de la forma:
2.- Eliminar el axioma de la derecha: Si el axioma S aparece en la 
derecha de alguna producción y S *  , entonces se realiza el
siguiente artificio: 
2.1.- se introduce un nuevo axioma o símbolo inicial S1
2.2.- se agrega a las producciones originales las reglas: S1 → S | 
S * wN (GRder) S * Nw (GRizq)
N* w
N → N
Lenguajes-Gramáticas Regulares 
y Autómatas Finitos. 
ING. JORGE BUABUD
U.T.N. – F.R.T. 
S. y S. de los L. 
GRAMÁTICAS REGULARES (GR):
3.- Eliminar reglas de redenominación: Se reemplaza las producciones 
de la forma N1→ N2 , por las reglas que surgen de reemplazar en las 
mismas N2 por las partes derechas de sus producciones.
4.- Eliminar reglas de borrado: Se reemplaza las producciones de la
forma N→  , por las reglas que surgen de reemplazar N por , 
en todas las reglas donde figure N; a excepción de la regla S →  ,
donde S es el axioma.
5.- Reducción de longitud: Se reemplaza las reglas de la forma
N1 → t1t2...tKW por las reglas N1→t1M1 , M1→t2M2 , .... , MK-1→ tKW 
donde los Mi son nuevos no-terminales, los ti son terminales, N1 es un
no-terminal y W puede ser un no-terminal o vacío (en forma similar
para una GR regular por la izquierda).
Lenguajes-Gramáticas Regulares 
y Autómatas Finitos. 
ING. JORGE BUABUD
U.T.N. – F.R.T. 
S. y S. de los L. 
GRAMÁTICAS REGULARES (GR):
Ejemplo de obtención del formato estándar de una GR:
Supongamos la siguiente GR por la derecha:
S → abaB | bb |  | A
A → baS | aabC | a
B → aaA | B | 
C → baC | aC
D → bbB | aaa | abaD
E → aaE | abC
G =  N , T , S , P 
N = {S, A, B, C, D, E}
T = {a, b}
P =
Lenguajes-Gramáticas Regulares 
y Autómatas Finitos. 
ING. JORGE BUABUD
U.T.N. – F.R.T. 
S. y S. de los L. 
GRAMÁTICAS REGULARES (GR):
1) Eliminación de reglas innecesarias:
S → abaB | bb |  | A
A → baS | a
B → aaA | 
S1 → S | 
S → abaB | bb |  | A
A → baS | a
B → aaA | 
2) Eliminación del axioma a la derecha: 
Lenguajes-Gramáticas Regulares 
y Autómatas Finitos. 
ING. JORGE BUABUD
U.T.N. – F.R.T. 
S. y S. de los L. 
GRAMÁTICAS REGULARES (GR):
3) Eliminación de reglas de redenominación:
S1 → abaB | bb | baS | a | 
S → abaB | bb |  | baS | a
A → baS | a
B → aaA | 
4) Eliminación de reglas de borrado:
S1 → abaB | bb | baS | a |  | ba | aba
S → abaB | bb | baS | a | ba | aba
A → baS | a | ba
B → aaA
Lenguajes-Gramáticas Regulares 
y Autómatas Finitos. 
ING. JORGE BUABUD
U.T.N. – F.R.T. 
S. y S. de los L. 
GRAMÁTICAS REGULARES (GR):
5) Reducción de la longitud:
S1 → aF | bH | bI | a |  | bJ | aK
F → bG
G → aB
H → b
I → aS
J → a 
K → bJ
S → aF | bH | bI | a | bJ | aK
A → bI | a | bJ
B → aL
L → aA
Los otros componentes de G:
N = { S1, A, B, F, G, H, I, J, K, L, S}
T = {a, b}
donde S1 es el nuevo axioma
Lenguajes-Gramáticas Regulares 
y Autómatas Finitos. 
ING. JORGE BUABUD
U.T.N. – F.R.T. 
S. y S. de los L. 
GRAMÁTICAS REGULARES (GR):
Equivalencia entre GR por derecha y GR por izquierda:
Los dos formatos posibles para una GR son equivalentes. 
Veamos un algoritmo para pasar del formato por izquierda al formato 
por derecha, partiendo de una GR en su forma estándar:
1.- Si el axioma figura en alguna parte derecha de las reglas, se procede 
a transformar la GR de la siguiente forma:
1.1.- Agregar un nuevo símbolo no-terminal L
1.2.- Si S es el axioma, tT y NN , entonces:
1.2.1.- Para cada regla de la forma S → Nt o S → t 
se crea una regla L → Nt o L → t 
1.2.2.- Cada regla de la forma N → St
se cambia por la regla N → Lt
Lenguajes-Gramáticas Regulares 
y Autómatas Finitos. 
ING. JORGE BUABUD
U.T.N. – F.R.T. 
S. y S. de los L. 
GRAMÁTICAS REGULARES (GR):
2.- Se crea un grafo dirigido:
2.1.- Se crea un nodo para cada no-terminal N y otro para 
2.2.- Para cada regla de la forma N1 → N2t
se crea un arco desde el nodo N1 al nodo N2 con rótulo t
2.3.- Para cada regla de la forma N → t
se crea un arco desde el nodo N al nodo  con etiqueta t
2.4.- Si existe una regla S → 
se crea un arco sin rótulo desde el nodo S al nodo 
3.- Se transforma este grafo de la siguiente manera:
3.1.- Se intercambian las etiquetas de los nodos S y 
3.2.- Se invierte el sentido de todos los arcos
Lenguajes-Gramáticas Regulares 
y Autómatas Finitos. 
ING. JORGE BUABUD
U.T.N. – F.R.T. 
S. y S. de los L. 
GRAMÁTICAS REGULARES (GR):
4.- Se transforma el grafo en un conjunto de reglas:
4.1.- Para cada arco etiquetado con t que va del nodo N1 al nodo N2
se crea la regla N1 → tN2
4.2.- Para cada arco etiquetado con t que va del nodo N al nodo 
se crea la regla N → t
4.3.- Si existe un arco del nodo del axioma S al nodo de 
se crea una regla S → 
En forma similar se puede definir un algoritmo para 
transformar una GR por derecha en su formato por 
izquierda equivalente.
Lenguajes-Gramáticas Regulares 
y Autómatas Finitos. 
ING. JORGE BUABUD
U.T.N. – F.R.T. 
S. y S. de losL. 
Ejemplo de conversión de GR por Izquierda a Derecha:
Supongamos una GR por izquierda con las siguientes producciones:
S → Ba | Ab , A → Sa | Ab , B → Bb | a
1.- Agregamos un nuevo no-terminal C y las reglas:
S → Ba | Ab , A → Ca | Ab , B → Bb | a
C → Ba | Ab
2.- Grafo:
GRAMÁTICAS REGULARES (GR):
b
S
A
B
C
a a
b a
a
b b
Lenguajes-Gramáticas Regulares 
y Autómatas Finitos. 
ING. JORGE BUABUD
U.T.N. – F.R.T. 
S. y S. de los L. 
3) Transformamos el grafo:
4) Creamos las reglas de la GR por la derecha a partir del grafo:
S → aB
A → bC | bA | b
B → aC | bB | a
C → aA
b

A
B
C
Sa a
b a
a
b b
GRAMÁTICAS REGULARES (GR):
Lenguajes-Gramáticas Regulares 
y Autómatas Finitos. 
ING. JORGE BUABUD
U.T.N. – F.R.T. 
S. y S. de los L. 
LENGUAJES REGULARES (LR):
Lenguaje Regular (LR):
Un LR es el lenguaje generado por una GR y se define mediante 
las siguientes cláusulas:
1) Todo lenguaje finito es un LR
2) Si L1 y L2 son LR entonces L1L2 y L1.L2 también son LR
3) Si L es un LR entonces L* también es un LR
4) Todo LR se puede definir mediante las cláusulas 1, 2 y 3
Lenguajes-Gramáticas Regulares 
y Autómatas Finitos. 
ING. JORGE BUABUD
U.T.N. – F.R.T. 
S. y S. de los L. 
LENGUAJES REGULARES (LR):
Ejemplos de LR: Consideremos el alfabeto ={a, b}
L1 = { } = 
L2 = {} = L
L3 = {a, b}
L4 = {aa, ab, ba, bb} 
L5 = {, aba, aaa, bab, bbb}
L6 = L3 . L5  L4
L7 = L5* . L4
L8 = L4 . L4*
Lenguajes-Gramáticas Regulares 
y Autómatas Finitos. 
U.T.N. – F.R.T. 
S. y S. de los L. 
Ejemplo de GR por la Derecha para un componente léxico:
Consideremos el lenguaje compuesto por el conjunto de todos los 
identificadores válidos de un lenguaje de programación hipotético:
GR =  ΣN , ΣT , P , S 
ΣN = { I, R} ΣT = { a, ... , z, 0, ... , 9, _ } S = I
L(GR) = { a, ... , z, _ } . { a, ... , z, 0, ... , 9, _ }*
Aplicando las reglas de esta gramática se puede generar:
I  aR  a 
I  _R  _1R  _1hR  _1h
I  zR  z_R  z_5R  z_5pR  z_5p
P: I → aR | bR | … | zR | _R
R → aR | bR | … | zR | _R | 0R | 1R | … | 9R | λ
ING. JORGE BUABUD
Lenguajes-Gramáticas Regulares 
y Autómatas Finitos. 
U.T.N. – F.R.T. 
S. y S. de los L. 
Consideremos el lenguaje compuesto por el conjunto de todos los 
números naturales, incluido el 0:
GR =  ΣN , ΣT , P , S 
ΣN = { N, R} ΣT = { a, ... , z, 0, ... , 9, _ } S = N
L(GR) = { 0 }  { 1, 2, ... , 9 } . { 0, 1, ... , 9 }*
Aplicando las reglas de esta gramática se puede generar:
N  0 
N  R  1
N  R  R0  20
N  R  R3  R03  R703  4703
P: N → 0 | R
R → R0 | R1 | … | R9 | 1 | 2 | … | 9
ING. JORGE BUABUD
Ejemplo de GR por la Izquierda para un componente léxico:
Lenguajes-Gramáticas Regulares 
y Autómatas Finitos.