UNIVERSIDAD TECNOLÓGICA NACIONAL Facultad Regional Tucumán Departamento: SISTEMAS
Cátedra: Sintaxis y Semántica de los Lenguajes Ciclo 2012 / 2013
TRABAJO PRÁCTICO Nº 2
Página 1
UNIDAD Nº 2: Gramáticas y Modelos Matemáticos Jerarquía de Chomsky y formatos estándares para tipos 0 y 1. Los aceptores de lenguajes formales: MT y ALL. Construcción de una MT.
2.1. Para cada conjunto de producciones:
• Completar la gramática • Indicar a que tipo de gramáticas corresponden en la Jerarquía de Chomsky, justificando la respuesta. • Obtener 3 palabras de longitud > 4 generadas por la gramática • Obtener 3 cadenas de longitud >4 que no se puedan generar • Enunciar el lenguaje generado.
a) G = ⟨⟨⟨⟨ΣN , ΣT , P , S ⟩⟩⟩⟩ ΣN = {S, X, Z} ΣT = {a, b, c} P:
1. S → Saa / Xb 2. X → Xb / Z 3. Z → Zcc / c
Gramática Tipo 3 Regular por Izquierda: Se cumple que todas las producciones tienen la forma: N1 →N2w N → w Donde N∈ΣN y w∈ΣT
* Derivaciones: S ⇒1 Saa ⇒1 Xbaa ⇒2 Zbaa ⇒3 Zccbaa ⇒3 cccbaa S ⇒1 Xb ⇒2 Xbb ⇒2 Zbb ⇒3 Zccbb ⇒3 Zccccbb ⇒3 cccccbb S ⇒1 Saa ⇒1 Saaaaa ⇒1 Xbaaaa ⇒2 Xbbaaaa ⇒2 Xbbbaaaa ⇒2 Zbbbaaaa ⇒3 cbbbaaaa Ejemplos de cadenas que no se pueden generar: cbaaa, cccaa, ccbaa cbaaa: S ⇒1 Saa ⇒1 Saaaa cccaa: S ⇒1 Saa ⇒1 Xbaa ccbaa: S ⇒1 Saa ⇒1 Xbaa ⇒2 Zbaa ⇒3 Zccbaa ⇒3 cccbaa L= { c2r+1 bn a2m / r ≥≥≥≥ 0, n ≥≥≥≥ 1, m ≥≥≥≥ 0 }
b) G = ⟨⟨⟨⟨ΣN , ΣT , P , S⟩⟩⟩⟩ ΣN = {S, A, B, X, Y, Z, T} ΣT = {a, b} P:
1. S → AB / XY / ZT / λ 2. A → XY / XZ 3. Y → AZ 4. B → ZT / ZX 5. T → BX 6. X → a 7. Z → b
2. Problemas a resolver por los alumnos en grupo
UNIVERSIDAD TECNOLÓGICA NACIONAL Facultad Regional Tucumán Departamento: SISTEMAS
Cátedra: Sintaxis y Semántica de los Lenguajes Ciclo 2012 / 2013
TRABAJO PRÁCTICO Nº 2
Página 2
Gramática Tipo 2: 1. No es gramática de Tipo 3 GR, pues no se cumple que todas las producciones tengan la forma N1 → N2w o N1 → wN2
N → w N→ w Donde N∈ΣN y w∈ΣT
* 2. Es gramática de Tipo 2 GIC: Se cumple en todas las producciones que α es un no terminal. Derivaciones: S ⇒ XY ⇒ aY ⇒ aAZ ⇒ aAb ⇒ aXYb ⇒ aaYb ⇒ aaAZb ⇒ aaAbb ⇒ aaXZbb ⇒ aaaZbb ⇒ aaabbb S ⇒ ZT ⇒ bT ⇒ bBX ⇒ bBa ⇒ bZTa ⇒ bbTa ⇒ bbBXa ⇒ bbBaa ⇒ bbZXaa ⇒ bbbXaa ⇒ bbbaaa S ⇒ AB ⇒ XYB ⇒ aYB ⇒ aAZB ⇒ aAbB ⇒ aXZbB ⇒ aaZbB ⇒ aabbB ⇒ aabbZX ⇒
aabbbX ⇒ aabbba Ejemplos de cadenas que no se pueden generar: aaabb, aaaaa, aabaa aaabb: S ⇒ XY ⇒ aY ⇒ aAZ ⇒ aAb ⇒ aXYb ⇒ aaYb ⇒ aaAZb ⇒ aaAbb ⇒ aaXZbb ⇒
aaaZbb ⇒ aaabbb aaaaa: S ⇒ XY ⇒ aY ⇒ aAZ ⇒ aAb aabaa: S ⇒ AB ⇒ XYB ⇒ aYB ⇒ aYZT ⇒ aYbT ⇒ aYbBX ⇒aYbBa ⇒ aAZbBa ⇒ aAbbBa L = {ambm+nan / m ≥≥≥≥ 0, n ≥≥≥≥ 0, m+n≠1 }
c) G = ⟨⟨⟨⟨ΣN , ΣT , P , S⟩⟩⟩⟩ ΣN = {S, A, B, C} ΣT = {a, b} P:
1. S → BAB 2. BA → BC 3. CA → AAC 4. CB → AAB 5. A → a 6. B → b
Gramática de Tipo 1 GDC: 1. No es gramática de Tipo 3 GR, ya que no se cumple este formato Ídem que 2.1.b 2. No es gramática de Tipo 2 GIC: No se cumple porque en las producciones 2, 3 y 4 α no es un no terminal. 3. Esta gramática es de Tipo 1 GDC: Se cumple en todas las producciones que Long(β) ≥≥≥≥ Long(α). Derivaciones: S ⇒BAB ⇒ BCB ⇒ BAAB ⇒ bAAB ⇒ baAB ⇒ baaB ⇒ baab
S ⇒ BAB ⇒ BCB ⇒ BAAB ⇒ BCAB ⇒ BAACB ⇒ BAAAAB ⇒* baaaab
S ⇒BAB ⇒ BCB ⇒ BAAB ⇒ BCAB ⇒ BAACB ⇒ BAAAAB ⇒ BCAAAB ⇒ BAACAAB ⇒ BAAAACAB ⇒ BAAAAAACB ⇒BAAAAAAAAB ⇒*baaaaaaaab
UNIVERSIDAD TECNOLÓGICA NACIONAL Facultad Regional Tucumán Departamento: SISTEMAS
Cátedra: Sintaxis y Semántica de los Lenguajes Ciclo 2012 / 2013
TRABAJO PRÁCTICO Nº 2
Página 3
Ejemplos de cadenas que no se pueden generar: aaaaa, babab, baaab
aaaaa: S ⇒ BAB ⇒ BCB ⇒ BAAB ⇒ BCAB ⇒ BAACB ⇒ bAACB
babab: S ⇒ BAB ⇒ BCB ⇒ BAAB ⇒ BCAB ⇒ BAACB ⇒ bAACB ⇒ bAaCB
baaab: S ⇒BAB ⇒ BCB ⇒ BAAB ⇒ BCAB ⇒ BAACB ⇒ BAAAAB L = {b ak b / k=2n con n≥≥≥≥0} d) S → SXZ / a ZX → XZ Z → b X → a ab → λ No es gramática de ningún tipo porque no todas las producciones cumplen con la condición de por lo menos un No Terminal en el lado izquierdo de la producción.
e) G = ⟨⟨⟨⟨ΣN , ΣT , P , S⟩⟩⟩⟩ ΣN = {S, X} ΣT = {a, b} P:
1. S → aXS / a 2. X → Xb 3. Xb → bX 4. bXb → bbb
Gramática de Tipo 1 GDC: 1. No es gramática de Tipo 3 GR: ya que no se cumple este formato Ídem que 2.1.b
2. No es gramática de Tipo 2 GIC: No se cumple porque en la producción 3 y 4 α no es un no terminal.
3. Esta gramática es de Tipo 1 GDC: Se cumple en todas las producciones que Long(β) ≥≥≥≥ Long(α). Derivaciones:
S ⇒ aXS ⇒ aXa ⇒ aXba ⇒ abXa ⇒ abXba ⇒ abbba
S ⇒ aXS ⇒ aXa ⇒ aXba ⇒ aXbba ⇒ abXba ⇒ abXbba ⇒abbbba
S ⇒ aXS ⇒ aXaXS ⇒ aXaXa ⇒ aXbaXa ⇒ aXbbaXa ⇒ abXbaXa ⇒ abbbaXa ⇒ abbbaXba ⇒ abbbaXbba ⇒ abbbaXbbba ⇒ abbbaXbbbba ⇒ abbbabXbbba ⇒ abbbabbbbba
Ejemplos de cadenas que no se pueden generar: babbba, abbbab, aabba
babbba: S ⇒ aXS
abbbab: S ⇒ aXS ⇒ aXa
aabba: S ⇒ aXS ⇒ aXa ⇒ aXba ⇒ aXbba ⇒ abXba
L = { lenguaje formado por todas las secuencias de ‘a’ y ‘b’ que comiencen y terminen con ‘a’ y entre dos ‘a’ debe haber por lo menos 3 ‘b’ }
UNIVERSIDAD TECNOLÓGICA NACIONAL Facultad Regional Tucumán Departamento: SISTEMAS
Cátedra: Sintaxis y Semántica de los Lenguajes Ciclo 2012 / 2013
TRABAJO PRÁCTICO Nº 2
Página 4
f) G = ⟨⟨⟨⟨ΣN , ΣT , P , S⟩⟩⟩⟩ ΣN = {S, X, Y, Z} ΣT = {a, b} P:
1. S → aSX / bSX / aY / bZ 2. X → a / b 3. Y → a 4. Z → b
Gramática Tipo 2: 1. No es gramática de Tipo 3 GR: ya que no se cumple este formato Ídem que 2.1.b
2. Es gramática de Tipo 2 GIC: Se cumple en todas las producciones que α es un no terminal. Derivaciones:
S ⇒ aSX ⇒ aaSXX ⇒ aabZXX ⇒aabbXX ⇒ aabbaX ⇒ aabbab
S ⇒ bSX ⇒ baSXX ⇒ babSXXX ⇒ babaYXXX ⇒babaaXXX ⇒ babaabXX ⇒babaabbX ⇒ babaabba
S ⇒ asX ⇒ abSXX ⇒ abbSXXX ⇒ abbbZXXX ⇒ abbbbXXX ⇒ abbbbbXX ⇒ abbbbbbX ⇒ abbbbbbb Ejemplos de cadenas que no se pueden generar: bababa, aba, aabba
bababa: S ⇒ bSX⇒baSXX⇒ babZXX ⇒ babbXX
aba: S ⇒ aSX ⇒ abZX ⇒ abbX
aabba: S ⇒ aSX ⇒ aaSXX⇒ aabZXX ⇒aabbXX⇒aabbaX L={ “Todas las secuencias de “a” y “b” de longitud par cuyos 2 símbolos centrales son iguales” }
g) G = ⟨⟨⟨⟨ΣN , ΣT , P , S⟩⟩⟩⟩ ΣN = {S, A, B, X} ΣT = {a, b} P:
1. S → bXa / ba 2. X → BXa / bb 3. BX → XBB 4. BBa → baa 5. A → a Observamos que esta última regla es inútil puesto que el no terminal A nunca aparece a la derecha de ninguna producción
Gramática de Tipo 1 GDC:
1. No es gramática de Tipo 3 R: ya que no se cumple este formato Ídem que 2.1.b
2. No es gramática de Tipo 2 GIC: No se cumple porque en la producción 3 y 4 α no es un no terminal.
3. Esta gramática es de Tipo 1 GDC: Se cumple en todas las producciones que Long(β) ≥≥≥≥ Long(α).
Derivaciones:
S ⇒ bXa ⇒ bBXaa ⇒ bXBBaa ⇒ bbbBBaa ⇒ bbbbaaa
S ⇒ bXa ⇒ bBXaa ⇒ bXBBaa ⇒ bBXaBBaa ⇒ bXBBaBBaa ⇒ bbbBBaBBaa ⇒ bbbbaaBBaa ⇒ bbbbaabaaa
S ⇒ bXa ⇒ bBXaa ⇒ bXBBaa ⇒ bBXaBBaa ⇒ bXBBaBBaa ⇒ bBXaBBaBBaa ⇒ bXBBaBBaBBaa ⇒ bbbBBaBBaBBaa ⇒ bbbbaaBBaBBaa ⇒bbbbaabaaBBaa ⇒ bbbbaabaabaaa
UNIVERSIDAD TECNOLÓGICA NACIONAL Facultad Regional Tucumán Departamento: SISTEMAS
Cátedra: Sintaxis y Semántica de los Lenguajes Ciclo 2012 / 2013
TRABAJO PRÁCTICO Nº 2
Página 5
Ejemplos de cadenas que no se pueden generar: aba, bbbbab, bbba
aba: S ⇒ bXa
bbbbab: S ⇒ bXa ⇒ bBXaa
bbbab: S ⇒ bXa ⇒ bbba L ={ “ba” y todas las palabras de la forma: b3 (baa)n a con n>=0 }
h) G = ⟨⟨⟨⟨ΣN , ΣT , P , S⟩⟩⟩⟩ ΣN = {S, X} ΣT = {a, b} P:
1. S → aXb 2. X → aXbb 3. Xb → bbb 4. aX → a
Gramática de Tipo 0 GI:
1. No es gramática de Tipo 3 GR: ya que no se cumple este formato Ídem que 2.1.b
2. No es gramática de Tipo 2 GIC: No se cumple porque en la producción 3 y 4 α no es un no terminal.
3. No es gramática de Tipo 1 GDC: No se cumple en la producción 4 que Long(β) ≥≥≥≥ Long(α).
4. Es gramática de Tipo 0: En todas las producciones α contiene, por lo menos, un No Terminal. Derivaciones:
S ⇒1 aXb ⇒4 ab
S ⇒1 aXb ⇒2 aaXbbb ⇒4 aabbb
S ⇒1 aXb ⇒2 aaXbbb ⇒2 aaaXbbbbb ⇒3 aaabbbbbbb Ejemplos de cadenas que no se pueden generar: aba, abbbab, bbbab
aba: S ⇒ aXb
abbbab: S ⇒ aXb⇒ aaXbbb
bbbab: S ⇒ aXb L = {a am (bb)n+m b / m ≥ 0 ; n = 0 , 1 }
i) G = ⟨⟨⟨⟨ΣN , ΣT , P , S⟩⟩⟩⟩ ΣN = {S, X} ΣT = {a, b} P:
1. S → aX / λ 2. X → aX / Xb /a
UNIVERSIDAD TECNOLÓGICA NACIONAL Facultad Regional Tucumán Departamento: SISTEMAS
Cátedra: Sintaxis y Semántica de los Lenguajes Ciclo 2012 / 2013
TRABAJO PRÁCTICO Nº 2
Página 6
Gramática Tipo 2 GIC:
1. No es gramática es de Tipo 3 GR: ya que no se cumple este formato Ídem que 2.1.b
2. Es gramática de Tipo 2 GIC: Se cumple en todas las producciones que α es un no terminal. Derivaciones:
S ⇒ aX ⇒ aXb ⇒ aXbb ⇒ aXbbb ⇒ aabbb
S ⇒ aX ⇒ aaX ⇒ aaaX ⇒ aaaaX ⇒ aaaaa
S ⇒ aX ⇒ aaX ⇒ aaaX ⇒ aaaXb ⇒ aaaab Ejemplos de cadenas que no se pueden generar: aba, abbbab, bbbab
aba: S ⇒ aX ⇒ aXb
abbbab: S ⇒ aX⇒ aXb⇒ aXbb
bbbab: S ⇒ aX L = { a2+n bm / m ≥ 0 ; n ≥ 0 }
j) G = ⟨⟨⟨⟨ΣN , ΣT , P , S⟩⟩⟩⟩ ΣN = {S, X} ΣT = {a, b} P:
1. S → aX / bS / b 2. X → bS / b
Gramática Tipo 3 GR: Se cumple que todas las producciones tienen la forma N1 → wN2
N→ w Donde N∈ΣN y w∈ΣT
* Derivaciones: S ⇒ bS ⇒ bbS ⇒ bbbS ⇒ bbbbS ⇒ bbbbb
S ⇒ bS ⇒ baX ⇒ babS ⇒ babbS ⇒ babbaX ⇒ babbab
S ⇒ aX ⇒ abS ⇒ abaX ⇒ ababS ⇒ ababb Ejemplos de cadenas que no se pueden generar: aba, abbbaa, bbbab
aba: S ⇒ aX ⇒ abS ⇒ abaX
abbbaa: S ⇒ aX⇒ abS ⇒ abbS ⇒ abbbS ⇒ abbbaX⇒ abbbaX
bbaab: S ⇒ aX⇒ abS ⇒ abbS ⇒ abbaX ⇒ abbabS L = { todas las secuencias que terminan con “b” y no tienen “a” consecutivas }
UNIVERSIDAD TECNOLÓGICA NACIONAL Facultad Regional Tucumán Departamento: SISTEMAS
Cátedra: Sintaxis y Semántica de los Lenguajes Ciclo 2012 / 2013
TRABAJO PRÁCTICO Nº 2
Página 7
2.2. Para las gramáticas de tipo 0 y 1 del ejercicio anterior, obtener una gramática equivalente en formato estándar. Para las gramáticas de tipo 2 y 3, indicar si se encuentran o no en algún formato estándar. Justificar la respuesta. a) Gramática Tipo 3 GR: No se encuentra en formato estándar:
N1 → t N2 N∈∑N , t∈∑T N → t Permite S → λ siempre y cuando S no figure a la derecha de ninguna producción.
b) Gramática Tipo 2: Está en el formato estándar de Chomsky:
N1→ N2 N3 N∈∑N , t∈∑T. N → t Permite S → λ siempre y cuando S no figure a la derecha de ninguna producción.
c) Gramática Tipo 1 La producción que no cumple con el formato estándar es la 3: CA → AAC La reemplazamos por las siguientes producciones, donde X y Y son dos nuevos noterminales. CA → XA XA → XYC XYC → AYC AYC → AAC La gramática equivalente en formato estándar es la siguiente:
G = ⟨⟨⟨⟨ΣN , ΣT , P , S⟩⟩⟩⟩ ΣN = {S, A, B, C, X, Y} ΣT = {a, b} P:
1. S → BAB 2. BA → BC 3. CA → XA 4. XA → XYC 5. XYC → AYC 6. AYC → AAC 7. CB → AAB 8. A → a 9. B → b
e) Gramática Tipo 1 GDC
1. S → aXS / a 2. X → Xb 3. Xb → bX 4. bXb → bbb
La producción que no cumple con el formato es la 3: Xb → bX
UNIVERSIDAD TECNOLÓGICA NACIONAL Facultad Regional Tucumán Departamento: SISTEMAS
Cátedra: Sintaxis y Semántica de los Lenguajes Ciclo 2012 / 2013
TRABAJO PRÁCTICO Nº 2
Página 8
1º) La ponemos en formato estándar Tipo 0, donde B es un nuevo no-terminal
1. S → aXS / a 2. X → XB 3. XB → BX 4. BXB → BBB 5. B → b Tengamos en cuenta que al sustituir “b” por “B” en la regla 3, también se ven afectadas las reglas 2 y 4.
2º) La reemplazamos por las siguientes producciones, donde F y G son dos nuevos no-terminales. XB → FB FB → FG FG → BG BG → BX La gramática equivalente en formato estándar es la siguiente:
G = ⟨⟨⟨⟨ΣN , ΣT , P , S⟩⟩⟩⟩ ΣN = {S, X, B, G, F} ΣT = {a, b} P:
1. S → aXS / a 2. X → XB 3. XB → FB 4. FB → FG 5. FG → BG 6. BG → BX 7. BXB → BBB 8. B → b
f) Gramática Tipo 2 S → aSX / bSX / aY / bZ X → a / b Y → a Z → b Está en el formato estándar de Greibach
N → tω N∈∑N , t∈∑T, ω∈∑N*
g) Gramática de Tipo 1 GDC
1. S → bXa / ba 2. X → BXa / bb 3. BX → XBB 4. BBa → baa
Las producciones que no cumplen con el formato estándar son las 3 y 4. 1º) Ponemos en formato estándar tipo 0, donde E y F son dos nuevos no-terminales
UNIVERSIDAD TECNOLÓGICA NACIONAL Facultad Regional Tucumán Departamento: SISTEMAS
Cátedra: Sintaxis y Semántica de los Lenguajes Ciclo 2012 / 2013
TRABAJO PRÁCTICO Nº 2
Página 9
1. S → bXE / bE 2. X → BXE / bb 3. BX → XBB 4. BBE → FEE 5. E → a 6. F → b
2º) Las reemplazamos por las siguientes producciones, donde G, H, I, J, K son dos nuevos no-terminales BX → XBB BX → GX GX → GHB GHB → GBB GBB → XBB BBA → FEE BBE → IBE IBE → IJE IJE → IJK IJK → FJK FJK → FEK FEK → FEE La gramática equivalente en formato estándar es la siguiente:
G =⟨⟨⟨⟨ΣN , ΣT , P , S⟩⟩⟩⟩ ΣN = {S, B, X,E, F, G, H, I, J, K} ΣT = {a, b} P:
1. S → bXE / bE 2. X → BXE / bb 3. BX → GX 4. GX → GHB 5. GHB → GBB 6. GBB → XBB 7. BBE → IBE 8. IBE → IJE 9. IJE → IJK 10. IJK → FJK 11. FJK → FEK 13. FEK → FEE 14. E → a 15. F → b
h) Gramática Tipo 0
S → aXb X → aXbb Xb → bbb aX → a La gramática equivalente en formato estándar es la siguiente:
G = ⟨⟨⟨⟨ΣN , ΣT , P , S⟩⟩⟩⟩
UNIVERSIDAD TECNOLÓGICA NACIONAL Facultad Regional Tucumán Departamento: SISTEMAS
Cátedra: Sintaxis y Semántica de los Lenguajes Ciclo 2012 / 2013
TRABAJO PRÁCTICO Nº 2
Página 10
ΣN = {S, X, A, B} ΣT = {a, b} P:
1. S → AXB 2. X → AXBB 3. XB → BBB 4. AX → A 5. A → a 6. B → b
i) Gramática Tipo 2 S → aX / λ X → aX / Xb /a Casi está en formato estándar de Greibach, pero la producción X → Xb no cumple con el formato:
N → tω N∈∑N , t∈∑T, ω∈∑N*
j) Gramática Tipo 3
S → aX / bS / b X → bS / b
Está en formato estándar: N1 → t N2 Ni∈∑N , t∈∑T N → t
2.3. Indicar para cada una de las gramáticas del ejercicio 2.1 si generan o no la palabra vacía; en los casos negativos, realizar las transformaciones necesarias para que la generen manteniendo el tipo de gramática. a) NO S1 → S / λ S → Saa / Xb X → Xb / Z Z → Zcc / c
b) SI S → AB / XY / ZT / λ A → XY / XZ Y → AZ B → ZT / ZX T → BX X → a Z → b
c) NO S → BAB / λ BA → BC CA → AAC CB → AAB A → a B → b e) NO S1 → S / λ S → aXS / a X → Xb
UNIVERSIDAD TECNOLÓGICA NACIONAL Facultad Regional Tucumán Departamento: SISTEMAS
Cátedra: Sintaxis y Semántica de los Lenguajes Ciclo 2012 / 2013
TRABAJO PRÁCTICO Nº 2
Página 11
Xb → bX bXb → bbb f) NO S1 → S / λ S → aSX / bSX / aY / bZ X → a / b Y → a Z → b g) NO S → bXa / ba / λ X → BXa / bb BX → XBB BBa → baa h) NO S → aXb / λ X → aXbb Xb → bbb aX → a i) SI S → aX / λ X → aX / Xb /a j) NO S1 → S / λ S → aX / bS / b X → bS / b 2.4. Encontrar una gramática de tipo 2 en FNC que genere el siguiente lenguaje: L = { an cm / n > m }
G = ⟨⟨⟨⟨ΣN , ΣT , P , S⟩⟩⟩⟩ ΣN = {S, T, C, A} ΣT = {a, c} P: S → a / TC / AS T → AS C → c A → a 2.5. Encontrar una gramática de tipo 2 en FNG que genere el siguiente lenguaje L = {todos los palíndromos sobre Σ = { a , b } cuya longitud sea impar }
G =⟨⟨⟨⟨ΣN , ΣT , P , S⟩⟩⟩⟩ P: S → aSA / bSB / a / b ΣN = {S, A, B} A → a ΣT = {a, b} B → b 2.6. Encontrar una gramática de tipo 3 en FNC que genere cada uno de los siguientes lenguajes
• L = { todas las secuencias sobre Σ = { a , b } que tengan una cantidad impar de “a" }
UNIVERSIDAD TECNOLÓGICA NACIONAL Facultad Regional Tucumán Departamento: SISTEMAS
Cátedra: Sintaxis y Semántica de los Lenguajes Ciclo 2012 / 2013
TRABAJO PRÁCTICO Nº 2
Página 12
G = ⟨⟨⟨⟨ΣN , ΣT , P , S⟩⟩⟩⟩ ΣN = {S, X} ΣT = {a, b} P: S → aX / bS / a X → aS / bX / b
• L = {todas las secuencias Σ = { a , b } con cantidad impar de “a" y cantidad impar de “b” }
G = ⟨⟨⟨⟨ΣN , ΣT , P , S⟩⟩⟩⟩ ΣN = {S, X, Y, Z} ΣT = {a, b} P: S → aX / bY X → aS / bZ / b Y → aZ / bS / a Z → aY / bX
2.7. Encontrar una gramática regular por la izquierda que genere el siguiente lenguaje L = { an bm cp / n > 2 , m impar , p ≥ 0}
G = ⟨⟨⟨⟨ΣN , ΣT , P , S⟩⟩⟩⟩ ΣN = {S, X, Y, Z, A} ΣT = {a, b} P: S → X / Sc X → Yb / Zb Y → Xb Z → Aaa A → Aa / a 2.8. Analizar las siguientes Máquinas, indicar de qué tipo de máquina se trata, definir sus componentes, detallar las secuencias de configuración de tres palabras aceptadas y tres palabras rechazadas. Definir el lenguaje que acepta y describir las secuencias de salida. a) TABLA DE TRANSICION
Estado Actual
Símbolo Entrada
Nuevo estado
Símbolo salida
Movimiento cabezal
→ A a B X D A Y E a D B a B a D B b B b D B > C > I B Y C Y I C b D Y I D a D a I D b D b I D X A b D E Y E a D E > F > I
* --- F --- --- --- ---
UNIVERSIDAD TECNOLÓGICA NACIONAL Facultad Regional Tucumán Departamento: SISTEMAS
Cátedra: Sintaxis y Semántica de los Lenguajes Ciclo 2012 / 2013
TRABAJO PRÁCTICO Nº 2
Página 13
- Se trata de un Autómata Linealmente Limitado
- ΣE = { a , b } ; ΣA = { X,Y , < , > }
- Secuencias de configuración de 3 palabras aceptadas
• ab <Aab> |— < XBb> |— <XbB> |— <XCb> |— <DXY> |— <bAY> |— < baE> |— <bFa> final: ACEPTA
• aabb <Aaabb> |— < XBabb> |— < XaBbb> |— < XabBb> |— <XabbB> |— <XabCb> |— <XaDbY> |— <XDabY> |— <DXabY> |— <bAabY> |— <bXBbY> |— <bXbBY> |— <bXCbY> |— <bDXYY> |— < bbAYY> |— <bbaEY> |— <bbaaE> |— <bbaFa> final: ACEPTA
• aaabbb
<Aaaabbb> |— < XBaabbb> |— < XaBabbb> |— < XaaBbbb> |— < XaabBbb> |— <XaabbBb> |— <XaabbbB> |— <XaabbCb> |— <XaabDbY> |— <XaaDbbY> |— <XaDabbY> |— <XDaabbY> |— <DXaabbY> |— <bAaabbY> |— <bXBabbY> |— <bXaBbbY> |— <bXabBbY> |— <bXabbBY> |— <bXabCbY> |— <bXaDbYY> |— <bXDabYY> |— <bDXabYY> |— <bbAabYY> |— <bbXBbYY> |— <bbXbBYY> |— <bbXCbYY> |— <bbDXYYY> |— <bbbAYYY> |— <bbbaEYY> |— <bbbaaEY> |— <bbbaaaE> |— <bbbaaFa> final: ACEPTA
- Secuencias de configuración de 3 palabras rechazadas
• λ <A> bloqueo: RECHAZA
• aab <Aaab> |— <XBab > |— <XaBb > |— <XabB > |— <XaCb > |— <XDaY > |— <DXaY > |— <bAaY > |— <bXBY > |— <bCXY > bloqueo: RECHAZA
• abb <Aabb> |— <XBbb> |— <XbBb> |— <XbbB> |— <XbCb> |— <XDbY> |— <DXbY> |— <bAbY> bloqueo: RECHAZA
- Lenguaje aceptado = {ambm / m ≥≥≥≥ 1} - La secuencia de salida consiste en la inversa de la entrada.
A
B
F
C
E
D
a, X, D
a, a, D
Y, a, D
b, b, D
Y, Y, I
>, >, I
b, Y, I
a, a, I
b, b, I
X, b, D
Y, a, D
>, >, I
UNIVERSIDAD TECNOLÓGICA NACIONAL Facultad Regional Tucumán Departamento: SISTEMAS
Cátedra: Sintaxis y Semántica de los Lenguajes Ciclo 2012 / 2013
TRABAJO PRÁCTICO Nº 2
Página 14
b) TABLA DE TRANSICION
Estado Actual
Símbolo Entrada
Nuevo estado
Símbolo salida
Movimiento cabezal
→ A b A b D A a C X D A Z B a D B Z B a D B ∆ E ∆ I C a C a D C b C b D C Z C Z D C ∆ D Z I D a D a I D b D b I D Z D Z I D X A a D
* -------E ----- ----- ----- -----
- Se trata de una Máquina de Turing
- ΣE = { a , b } ; ΣA = { X,Z , ∆}
- Secuencias de configuración de 3 palabras aceptadas
• ab ∆Aab∆ |— ∆XCb∆ |— ∆XbC∆ |— ∆XDbZ |— ∆DXbZ∆ |— ∆aAbZ∆ |— ∆abAZ∆ |— ∆abaB∆ |— ∆abEa∆ final: ACEPTA
• aabb ∆Aaabb∆ |— ∆XCabb∆ |— ∆XaCbb∆ |— ∆XabCb∆ |— ∆XabbC∆ |— ∆XabDbZ |— ∆XaDbbZ |— ∆XDabbZ |— ∆DXabbZ |— ∆aAabbZ |— ∆aXCbbZ |— ∆aXbCbZ |— ∆aXbbCZ |— ∆aXbbZC∆ |— ∆aXbbDZZ∆ |— ∆aXbDbZZ∆ |— ∆aXDbbZZ∆ |— ∆aDXbbZZ∆ |— ∆aaAbbZZ∆ |— ∆aabAbZZ∆ |— ∆aabbAZZ∆ |— ∆aabbaBZ∆ |— ∆aabbaaB∆ |— ∆aabbaEa∆ final: ACEPTA
A
C
E B
a, X, D
a, a, D
Z, a, D
b, b, D
b, b, D
Z, a, D
∆, ∆, I
Z, Z, D
∆, Z, I
D
a, a, I
b, b, I
Z, Z, I
X, a, D
UNIVERSIDAD TECNOLÓGICA NACIONAL Facultad Regional Tucumán Departamento: SISTEMAS
Cátedra: Sintaxis y Semántica de los Lenguajes Ciclo 2012 / 2013
TRABAJO PRÁCTICO Nº 2
Página 15
• bab ∆Abab∆ |— ∆bAab∆ |— ∆bXCb∆ |— ∆bXbC∆ |— ∆bXDbZ∆ |— ∆bXDbZ∆ |— ∆bDXbZ∆ |—
∆baAbZ∆ |— ∆babAZ∆ |— ∆babaB∆ |— ∆babEa∆ final: ACEPTA
- Secuencias de configuración de 3 palabras rechazadas
• λ ∆A∆ bloqueo: RECHAZA
• b ∆Ab∆ |— ∆bA∆ bloqueo:RECHAZA
• bb ∆Abb∆ |— ∆bAb∆ |— ∆bbA∆ bloqueo:RECHAZA
- Lenguaje aceptado = {Todas las secuencias de “a” y “b” no vacía, que contengan al menos una “a”} - La secuencia de salida es igual a la entrada concatenada con tantas “a” como “a” tenga la misma. 2.9. Obtener los ALL que acepten los siguientes lenguajes
• L = { todas las cadenas de Σ = { a , b } de longitud par cuyos símbolos “centrales” sean distintos}
A
B
G
C
E
D
b, Y, D
a, a, D
X, a, I
b, b, D
Y, Y, I
>, >, I
b, Y, I
a, a, I
b, b, I
Y, b, I
a, X, D X, X, I
a, X, I
Y, Y, D
X, X, D
F
Y, b, I
X, a, I
UNIVERSIDAD TECNOLÓGICA NACIONAL Facultad Regional Tucumán Departamento: SISTEMAS
Cátedra: Sintaxis y Semántica de los Lenguajes Ciclo 2012 / 2013
TRABAJO PRÁCTICO Nº 2
Página 16
• L = { an bm cn+m / n ≥≥≥≥ 0 , m ≥≥≥≥ 0 }
Nota: No debe permitirse que existan “a” después de la primera “b”. En ese caso, el ALL se bloqueará en el estado E. 2.10. Desarrollar Máquinas de Turing que realicen las siguientes acciones. ¿En qué casos podría encontrarse un ALL equivalente? Justifique su respuesta sin desarrollar los ALL a) invertir una palabra de longitud impar . ΣE = { a , b }
Para este caso es posible encontrar un ALL equivalente porque los desplazamientos en la cinta nunca sobrepasan los delimitadores de la palabra.
A
B C
D
(b, X, D)
(a, a, D)
(b, b, D)
(>, >, I)
(c, >, I)
(a, a, I)
(b, b, I)
(a, X, D) (c, c, D)
(X, X, D)
F
(c, c, I)
(>, >, I)
E
G
H
(b, b, I)
(c, c, I)
(c, c, D)
(b, b, D)
(>, >, I)
(c, >, I)
(X, X, D)
UNIVERSIDAD TECNOLÓGICA NACIONAL Facultad Regional Tucumán Departamento: SISTEMAS
Cátedra: Sintaxis y Semántica de los Lenguajes Ciclo 2012 / 2013
TRABAJO PRÁCTICO Nº 2
Página 17
b) A partir de un palíndromo de longitud impar obtener otro de longitud par “duplicando” el símbolo central (la nueva secuencia tendrá longitud n+1). ΣE = { a , b }
No es posible encontrar un ALL equivalente porque los desplazamientos en la cinta sobrepasarían el delimitador derecho al extender la longitud a n+1. c) Obtener la diferencia de dos números “unarios”. (la secuencia a agregar a continuación de las dos
originales será la diferencia entre la mayor longitud y la menor longitud)
Definiendo las secuencias de entrada como dos series de “1” separadas por el símbolo “-“, en la transformación deberíamos agregar un símbolo “=” y, a continuación, otra secuencia de “1” cuya longitud será la diferencia entre la mayor longitud y la menor longitud. ΣE = { 1 , - } Ejemplos Entrada: 11111-11 ; Salida 11111-11=111 Entrada: 111-1111 ; Salida 111-1111=1 Entrada: 111-111 ; Salida 111-111= (no existe el cero en sistema unario) Opción para el alumno: en los casos que la primera secuencia tenga menor longitud que la segunda, que el resultado sea negativo (incluir un signo “-“ después del “=”)
A
B C
D
(b, Y, D)
(a, a, D) (b, b, D)
(Δ,Δ,I)
(a,X,I)
(a, X, D)
E
F
H
(a,a,D)
(b,b,D)
(X,a,D)
(b,Y,I)
I
(Y,Y,I)
(a,a,I)
(b,b,I)
(Δ,Δ,I)
(X,X,I)
(Y,Y,I)
(Y,b,D)
G
(X,a,D)
(Y,b,D) (Y,b,D)
(X,a,D)
(X,b,D) (Y,a,D)
(Δ,b,D)
(Δ,a,I)
(X,X,I)
UNIVERSIDAD TECNOLÓGICA NACIONAL Facultad Regional Tucumán Departamento: SISTEMAS
Cátedra: Sintaxis y Semántica de los Lenguajes Ciclo 2012 / 2013
TRABAJO PRÁCTICO Nº 2
Página 18
No es posible encontrar un ALL equivalente porque los desplazamientos en la cinta sobrepasarían el delimitador derecho al agregar el signo “=” y la nueva cadena de “1”.
2.11. Desarrollar una Máquina de Turing que multiplique por 2 un número binario y posteriormente
invierta la cadena obtenida, eliminando los ceros no significativos que pudieran quedar a la izquierda
(desarrollar una máquina para cada transformación y combinarlas para obtener el resultado buscado)
En primer lugar se construye una MT1 que multiplique por 2 un número binario natural, esto es simplemente que le agregue un “0” al final, verificando que sea un secuencia de “0” y “1”; y teniendo en cuenta como caso particular el número “0”, en cuyo caso no debe hacer nada. En el caso de una secuencia que tenga ceros a la izquierda no significativos, será rechazada. Para poder combinarla con otra MT2 que haga la inversión, dejaremos el cabezal al principio de la secuencia. MT1 = < Q1 , ΣE , ΣA1 , q01 , F1 , f1 > Q1 = { q01 , q11 , q21 , q31 , q41 } ΣE = { 1, 0 } ΣA1 = { ∆ } F1 = { q41 }
A
B C
D
(-,-,D)
(1,1,D)
(-,-,D)
(1,Z,I)
(1, X, D)
E
F
J
(Z,1,D)
(X,1,D)
(Z,1,D)
(-,-,I)
(1,1,I)
(1,Z,D)
(1,1,D)
H
(Δ,=,D)
(Δ,=,D)
(Δ,=,-)
(=,=,D)
(-,-,D)
(Δ,1,I)
(X,1,D)
(1,1,I)
(Z,Z,D)
G
(1,1,I)
(Δ,-,I)
K
I
(1,1,D)
(-,-,D)
(-,-,I)
(Z,1,I)
(=,=,=)
(1, X, D)
L
(=,=,I) (-,-,I)
M
(1,1,D)
(=,=,D)
M
(-,-,D)
(1,Z,D)
(=,=,-)
(Δ,1,I)
UNIVERSIDAD TECNOLÓGICA NACIONAL Facultad Regional Tucumán Departamento: SISTEMAS
Cátedra: Sintaxis y Semántica de los Lenguajes Ciclo 2012 / 2013
TRABAJO PRÁCTICO Nº 2
Página 19
TABLA DE TRANSICIÓN DE f1
Estado Actual Símbolo Entrada Nuevo Estado Símbolo Salida Movimiento Cabezal
→ q01 1 q21 1 D
q01 0 q11 0 D
q11 ∆ q41 ∆ I
q21 1 q21 1 D
q21 0 q21 0 D
q21 ∆ q31 0 I
q31 1 q31 1 I
q31 0 q31 0 I
q31 ∆ q41 ∆ D
*q41 -------- -------- -------- --------
La Máquina MT2 hará la inversión de la secuencia, esta máquina la podemos plantear a partir de la MT del ejercicio 2.10-a, que invertía palabras de longitud impar, haciendo las siguientes transformaciones para que funcione con números binarios de longitud par o impar y deje al cabezal al principio de la secuencia:
1) Cambiar el alfabeto {a, b} por {0 ,1}
2) El estado H deja de ser final y se agrega el estado K como final, por lo tanto eliminamos la última fila de la tabla de transición.
3) Agregamos las siguientes transiciones:
Estado Actual Símbolo Entrada Nuevo Estado Símbolo Salida Movimiento Cabezal
→ A X K 0 I
A Y K 1 I
H 0 H 0 I
H 1 H 1 I
H ∆ K ∆ D
*K ------ ------ ------ ------
UNIVERSIDAD TECNOLÓGICA NACIONAL Facultad Regional Tucumán Departamento: SISTEMAS
Cátedra: Sintaxis y Semántica de los Lenguajes Ciclo 2012 / 2013
TRABAJO PRÁCTICO Nº 2
Página 20
Por último planteamos una MT3 que eliminará los “0” no significativos de la izquierda, teniendo en cuenta el caso particular del número “0”: MT3 = < Q3 , ΣE , ΣA3 , q03 , F3 , f3 > Q3 = { q03 , q13 , q23 , q33} ΣE = { 1, 0 } ΣA3 = { ∆ } F3 = { q33 }
TABLA DE TRANSICIÓN DE f3
Estado Actual Símbolo Entrada Nuevo Estado Símbolo Salida Movimiento Cabezal
→ q03 0 q13 0 D
q13 0 q23 0 I
q13 1 q23 1 I
q13 ∆ q33 ∆ I
→ q23 0 q23 ∆ D
q23 1 q33 1 N
*q33 -------- -------- -------- --------
Combinando MT1 con MT2 y MT3 se resuelve el problema planteado. Para lo cual se toma las tres MT y se las considera como una sola, con las siguientes transformaciones:
1) Los estados iniciales de MT2 y MT3 dejan de ser iniciales, el único inicial es el de la MT1. 2) Los estados finales de MT1 y MT2 dejan de ser finales, el único final es el de la MT3. 3) Se agrega una transición del final de MT1 al inicial de MT2 y del final de MT2 al inicial de
MT3, con etiqueta: (∆, ∆, N).