sales

Ciclo: 2013
integrantes:
Valdez Ivana
Molina cristian
Lopez damiano
2k6




TRABAJO PRACTICO Nº4









3.1 Encontrar GIC que generen los siguientes lenguajes:
a) L1 = {xn(y + z)n / n ≥ 0 }
S xSy / xSz / λ
b) L2 = { an+m bn cm / n,m ≥ 1 }
SaSc / aXc
XbXc / bc
c) L3 = { 0n 1m / n,m ≥ 1 , n=2m o m=2n }
S aaXb / aYb
X aaXb / a
YaYbb / λ

3.2 Para lasgramáticas obtenidas en el ejercicio anterior, seleccionar dos palabras de longitud mayor que 5 y dibujar los árboles de derivación correspondientes a cada una. Graficar los árboles totales de los lenguajes(considerar al menos 4 niveles de profundidad)

SxSyxxSyyxxxSyyyxxxyyy






























SxSzxxSzzxxxSzzzxxxzzz3.3 Encontrar los lenguajes generados por las siguientes GIC. Obtener gramáticas simplificadas para cada una y pasarlas a la Forma Normal de Chomsky
a)SaSa/aSb/A
AcBd
BcBd/d/λ

1) Obtener gramatica simplificada
Eliminar reglas innecesarias
SaSa/aSb/A
AcBd
BcBd/d/λ
Verificar S λ
SB λ a la larga
SaSa/aSb/A
AcBd
BcBd/d/ λ
Eliminar reglade borrado
SaSa/aSb/A/B
AcBd/cd
BcBd/d/cd
Eliminar reglas de renombrado
SaSa/aSb/A/cBd/d/cd
AcBd/cd
BcBd/d/cd

2) FNCHT0 y reducir longitud
SXF/XG/A/CI/D/CD
ACI/CDBCI/D/CD
Xa
FSa
GSb
Cc
IBd
Dd

b) SAB/BC
ASAa/aa
BSaa/λ
CBB/cCc

1) Obtener gramatica simplificada
Eliminar reglas innecesarias
SAB/BC
ASAa/aa
BSaa/λ
CBB/cCc
Eliminar regla deborrado
SAB/BC/A/C
ASAa/aa
BSaa
CBB/cCc
Eliminar reglas de renombrado
SAB/BC/SAa/aa/BB/cCc
ASAa/aa
BSaa
CBB/cCc

2) FNCHT0 y reducir longitud
SAB/BC/SD/E/BB/YF
ASD/E
BSECBB/YF
DAa
Eaa
Yc
FCc
3.4 Pasar a la Forma Normal de Greibach las siguientes GIC
Saa/T/λ
TbXb/aYa
XZb
YaYa/bYb
ZXb/aa

1) Obtener forma simplificada
Eliminar reglas...