UNIVERSIDAD TECNOLÓGICA NACIONAL
Facultad Regional Tucumán
TRABAJO PRÁCTICO
Departamento: SISTEMAS
Nº 2
Cátedra: Sintaxis y Semántica de los Lenguajes
Ciclo 2021
UNIDAD Nº2: Lenguajes-Gramáticas Regulares y Autómatas Finitos.
Gramáticas Regulares (GR), Lenguajes Regulares (LR), Expresiones Regulares (ER), Autómatas
Finitos Deterministas y No-Deterministas (AFD y AFND). Máquinas de Estados Finitos (MEF).
Analizador Léxico (Scanner).
1. Problemas a resolver en clase
1.1. Obtener una GR en formato estándar para el siguiente conjunto de producciones. En el
caso del punto b), pasar el FNC3 de regular izquierda a derecha. Simular con JFLAP.
a) P: S → abX | bbY | aaW | λ
T → baS | abY
V → aS | bbX | baY
X → abT | bbbS | aaZ
Y → T | aaX | λ
Z → abZ | bbZ
Aplicando el mecanismo para obtener una gramática regular en formato estándar.
1º paso: eliminar las reglas innecesarias
S → aaW
Esta regla es innecesaria, porque el no terminal W es inútil, ya que no puede derivar a nin-
guna secuencia de terminales, debido a que no hay reglas con W a la izquierda.
V → aS | bbX | baY
Estas reglas son innecesarias, porque el no terminal V es inútil, ya que no existe ninguna
sucesión de reglas a partir del axioma que permita llegar a V, debido a que V no está en la
parte derecha de ninguna regla.
Z → abZ | bbZ
X → aaZ
El no terminal Z es inútil porque nunca derivará secuencias de terminales solos, ya que con-
tiene solo reglas recursivas sin ningún caso base, lo que lleva a un ciclo infinito. Por lo tanto
todas las reglas que contienen Z son innecesarias.
Entonces las producciones quedan:
P: S → abX | bbY | λ
T → baS | abY
X → abT | bbbS
Y → T | aaX | λ
Página 1/7
UNIVERSIDAD TECNOLÓGICA NACIONAL
Facultad Regional Tucumán
TRABAJO PRÁCTICO
Departamento: SISTEMAS
Nº 2
Cátedra: Sintaxis y Semántica de los Lenguajes
Ciclo 2021
2º paso: eliminar el axioma S de la derecha, si es que λ L, es decir S→* λ y si el
axioma S aparece a la derecha de alguna producción
Se agrega un nuevo axioma S1, que obviamente no aparece en la parte derecha de ninguna
producción, y las reglas quedan:
S1→ S | λ
S → abX | bbY | λ
T → baS | abY
X → abT | bbbS
Y → T | aaX | λ
Donde la regla S1→ λ, será la excepción para generar la palabra vacía y no se eliminará en
el paso 4.
3º paso: eliminar reglas de redenominación N1→ N2
Para eliminar Y → T, se agregan las reglas: Y → baS | abY | aaX | λ
Para eliminar S1→ S se agregan las reglas: S1→ abX | bbY | λ
Las producciones quedan:
S1→ abX | bbY | λ
S → abX | bbY | λ
T → baS | abY
X → abT | bbbS
Y → baS | abY | aaX | λ
4º paso: eliminar reglas de borrado
Para eliminar “S → λ” y “Y → λ”, se agregan las nuevas producciones que surgen de reem-
plazar S y Y por λ en las partes derechas
S1→ abX | bbY | λ | bb
S → abX | bbY | bb
T → baS | abY | ba | ab
X → abT | bbbS | bbb
Y → baS | abY | aaX | ba | ab
5º paso: Realizar las sustituciones necesarias para reducir a uno la cantidad de termi-
nales en cada regla.
S1→ aC | bD | bB | λ C → bX
S → aC | bD | bB D → bY
T → bE | aD | bA | aB E → aS
X → aF | bG | bH F → bT
Y → bE | aD | aI| bA | aB G → bJ
A→a J → bS
B→b H → bB
I →aX
Página 2/7
UNIVERSIDAD TECNOLÓGICA NACIONAL
Facultad Regional Tucumán
TRABAJO PRÁCTICO
Departamento: SISTEMAS
Nº 2
Cátedra: Sintaxis y Semántica de los Lenguajes
Ciclo 2021
b)
P: S → Xa | Tabb | Y
T → Tba | Wab | Xaa
V → Tbb | Xabb | Yb
X → Ya | Xaba | λ
Y→T|λ
Z → Zab | Ybb | aaa
Aplicando el mecanismo para obtener una gramática regular en formato estándar.
1º paso: eliminar las reglas innecesarias
T → Wab (no se puede continuar)
V → Tbb | Xabb | Yb (no se pueden aplicar nunca)
Z → Zab | Ybb | aaa (no se pueden aplicar nunca)
Entonces las producciones quedan:
S → Xa | Tabb | Y
T → Tba | Xaa
X → Ya | Xaba | λ
Y→T|λ
2º paso: eliminar el axioma S de la derecha, si es que λ L, es decir S→* λ y si el
axioma S aparece a la derecha de alguna producción
No se agrega S1 → S | λ, porque si bien S → Y → λ, S no figura del lado derecho de ninguna
regla de producción. Pero se agrega la regla S → λ, para que siga generando la palabra
vacía; esta regla será la excepción y no se eliminará en el paso 4.
3º paso: eliminar reglas de redenominación N1→ N2
Para eliminar Y → T, se agregan las reglas: Y → Tba | Xaa | λ
Para eliminar S → Y, se agregan las reglas: S → Xa | Tabb | Tba | Xaa | λ
Página 3/7
UNIVERSIDAD TECNOLÓGICA NACIONAL
Facultad Regional Tucumán
TRABAJO PRÁCTICO
Departamento: SISTEMAS
Nº 2
Cátedra: Sintaxis y Semántica de los Lenguajes
Ciclo 2021
Las producciones quedan:
S → Xa | Tabb | Tba | Xaa | λ
T → Tba | Xaa
X → Ya | Xaba | λ
Y → Tba | Xaa | λ
4º paso: eliminar reglas de borrado
Para eliminar “X→ λ” y “Y → λ”, se agregan las nuevas producciones que surgen de reem-
plazar X y Y por λ en las partes derechas
S → Xa | Tabb | Tba | Xaa | a | aa | λ
T → Tba | Xaa | aa
X → Ya | Xaba | a | aba
Y → Tba | Xaa | aa
5º paso: Realizar las sustituciones necesarias para reducir a uno la longitud de las se-
cuencias de terminales que hubiera en las reglas.
S → Xa | Bb | Da | Ea | a | Aa | λ A →a E → Xa
B → Cb F → Eb
T → Da | Ea | Aa
C → Ta G → Ab
X → Ya | Fa | Ga | a D → Tb
Y → Da | Ea | Aa
Para convertir la Gramática regular por izquierda en Gramática regular por derecha, aplica-
remos el método correspondiente.
1) Dado que en este caso, el axioma no figura a la derecha de las reglas, no será nece-
sario hacer ninguna transformación previa a la GR.
2) Construir el siguiente grafo
Página 4/7
UNIVERSIDAD TECNOLÓGICA NACIONAL
Facultad Regional Tucumán
TRABAJO PRÁCTICO
Departamento: SISTEMAS
Nº 2
Cátedra: Sintaxis y Semántica de los Lenguajes
Ciclo 2021
Página 5/7
UNIVERSIDAD TECNOLÓGICA NACIONAL
Facultad Regional Tucumán
TRABAJO PRÁCTICO
Departamento: SISTEMAS
Nº 2
Cátedra: Sintaxis y Semántica de los Lenguajes
Ciclo 2021
3) Invertir el grafo
4) Crear las reglas de la GR por derecha a partir del grafo
S → aA | aX | a | λ A → aT | aY | bG | a E → aT | aY | bF | a
T → aC | bD B→b F → aX
X → aE | a C → bB G → aX
D → aY | aT | a
Y → aX
Como detalle de este caso particular, los No terminales F, G y Y tienen las mismas re-
glas por lo tanto se pueden unificar en uno solo, en este caso hemos tomado a Y.
Por otro lado observamos que al reemplazar G y F por Y, las reglas de A y E quedan
iguales, o sea que también se pueden unificar; entonces, si elegimos a A, la gramática
queda:
S → aA | aX | a | λ A → aT | aY | bY | a
T → aC | bD B→b
X → aA | a C → bB
Y → aX D → aY | aT | a
Página 6/7
UNIVERSIDAD TECNOLÓGICA NACIONAL
Facultad Regional Tucumán
TRABAJO PRÁCTICO
Departamento: SISTEMAS
Nº 2
Cátedra: Sintaxis y Semántica de los Lenguajes
Ciclo 2021
1.2 Encontrar gramáticas regulares a la derecha y a la izquierda que generen los lenguajes
indicados, considerando el alfabeto Σ = { a , b , c }. Simular con JFLAP
a) Todas las palabras que no tienen símbolos consecutivos iguales
S → aX | bY | cZ | λ S → Xa | Yb | Zc | λ
X→ bY | cZ | λ X → Yb | Zc | λ
Y→ aX| cZ | λ Y → Xa | Zc | λ
Z→ aX | bY | λ Z → Xa | Yb | λ
b) Todas la palabras que responden al patrón anbmcp / n≥0 , m impar , p≥2
S→ aS | X S → Sc | Xcc
X → bbX | bY X → Xbb | Yb
Y→ cY | cc Y → Ya | λ
Página 7/7
