Exercicis del RACSO online Resolts (2014)

Ejercicio Inglés
Universidad Universidad Politécnica de Cataluña (UPC)
Grado Ingeniería Informática - 3º curso
Asignatura Teoria de la computacio
Año del apunte 2014
Páginas 24
Fecha de subida 16/06/2014
Descargas 38
Subido por

Descripción

Exercicis del RACSO online de TC Resolts

Vista previa del texto

CFGs 1. CFG no ambigua para { a b ∣ n≥0 } n n S -> aSb | 2.
CFG no ambigua para { a c b ∣ n>0 } n n S-> aSb|aXb X-> c 3.
CFG no ambigua para { a b ∣ i≥j } i j S -> aSb|X X-> aX| 4.
CFG no ambigua para { a b ∣ i≤j } i j S-> aSb|X X-> Xb| 5.
CFG no ambigua para { a b ∣ 2i≤j } i j S-> aSbb|X X-> Xb| 6.
CFG para { a b ∣ 2i≥j } i j S-> aSbb|X X-> aXb|Y Y-> aY| 7.
CFG no ambigua para { a b ∣ 2i≥j } i j S -> aS | aBbb | ab | B -> aBbb | ab | 8.
CFG no ambigua para { a b ∣ j≤i≤2j } S -> aaSb | R R -> aRb | 9.
CFG no ambigua para { a b ∣ i≥j ∨ i≤2j } S -> aSb | A | B | A -> aA | a B -> bB | b i i j j 10.
CFG no ambigua para { a b c ∣ i=j+k } S -> aSc | R R -> aRb | i j k 11.
CFG no ambigua para { a b c ∣ j=i+k } S-> aRb | aRbbTc | bTc | R-> aRb | T-> bTc | i j k 12.
CFG para { a b c ∣ i=j ∨ j=k ∨ i=k } S->X|Y|Z| X->T|C T->aObC O->aOb| C->cC| i j k Y->U|B U->aUc|B B->bB| Z->I|A I->AbPc A->aA| P->bPc| 13.
CFG para { a b a b … a n₀ n₁ n m-1 ba n m ∣ m≥1 ∧ ∃ i∈{1,…,m}: (n₀ = n ) } i S-> XY Y-> bW | W-> aW | bW | X-> aXa| b | bWb 14.
CFG no ambigua para { a b a b … a n₀ n₁ n m-1 ba n m ∣ m≥1 ∧ (n₀ = ∑ 1≤i≤m n) } i S -> aSa | Sb | b 15.
CFG para { a b a b … a S -> MD | bC M -> AB A -> aMa | b | bCb B -> bB | bCb | D -> bC | C -> aC | bC | n₀ n₁ n m-1 ba n m ∣ m≥1 ∧ ∃ I⊆{1,…,m}: (n₀ = ∑ n ) } i∈I 16.
CFG no ambigua para { w ∈ {a,b}* ∣ w=w } S-> aSa | bSb | a | b | R 17.
CFG no ambigua para { w ∈ {a,b}* ∣ w=w ∧ |w| =0 } S -> aRa | bSb | a | b | R -> aRa | bTb | a | T -> bSb | b | R aba 18.
CFG no ambigua para { w ∈ {a,b}* ∣ w=w ∧ |w| >0 ∧ |w| >0 } S-> aRa | bTb R a b i R-> aRa | bXb | b T-> aXa | bTb | a X-> aXa | bXb | a | b | 19.
CFG no ambigua para { w ∈ {a,b}* ∣ w=w ∧ |w| >0 } S-> aRa | bSb R-> aRa | bTb | b T-> aXa | bSb | a X-> aXa | bXb | a | b | R aba 20.
CFG para palabras bien parentizadas sobre { ( , ) } S-> S(S)S | 21.
CFG para palabras bien parentizadas sobre { [ , ] , ( , ) } S-> S(S)S | S[S]S | 22.
CFG no ambigua para palabras bien parentizadas sobre { ( , ) } S-> (S)S | 23.
CFG no ambigua para palabras bien parentizadas sobre { [ , ] , ( , ) } S-> (S)S | [S]S | 24.
CFG para { w ∈ {a,b}* ∣ |w| =|w| } S-> aSbS | bSaS | a b 25.
CFG para { w ∈ {a,b,c}* ∣ |w| =|w| } S-> aSbS | bSaS | cS | a b 26.
CFG para { w ∈ {a,b,c}* ∣ |w| +|w| =|w| } S-> aScS | cSaS | cSbS | bScS | aSc | cSa | bSc | cSb | a b c 27.
CFG para { w ∈ {a,b}* ∣ 2|w| =|w| } S-> aSbSbS | bSaSbS | bSbSaS | a b 28.
CFG no ambigua para { w ∈ {a,b}* ∣ |w| =|w| } S -> aPbS | bNaS | P -> aPbP | N -> bNaN | a 29.
b CFG no ambigua para { w ∈ {a,b,c}* ∣ |w| =|w| } a b S -> aPbS | bNaS | cS | P -> aPbP | cP | N -> bNaN | cN | 30.
CFG no ambigua para { w ∈ {a,b,c}* ∣ |w| +|w| =|w| } S -> XPcS | cNXS | P -> XPcP | N -> cNXN | X -> a | b a b c 31.
CFG no ambigua para { w ∈ {a,b}* ∣ 2|w| =|w| } a b S -> aBBS | bAS | bCBS | B -> b | aBBB A -> bC | bAA C -> a | bAC 32.
CFG no ambigua para { xcy ∣ x,y∈{a,b}* ∧ |x| =|y| } a b S-> BaSbA | BcA A-> aA | B-> bB | 33.
CFG no ambigua para { xcy ∣ x,y∈{a,b}* ∧ |x| =|y| } ab ba S-> bS | aX | cE X-> aX | bY | cE Y-> Yb | Za Z-> Za | Sb E-> Eb | Fa | F-> Fa | 34.
CFG no ambigua para { xcy ∣ x,y∈{a,b}* ∧ |x| =|y| } aba bab 35.
CFG no ambigua para { xcy ∣ x,y∈{a,b}* ∧ y prefijo de x } S-> aSa | bSb | C C-> Rc R-> aR | bR | R 36.
CFG no ambigua para { xcy ∣ x,y∈{a,b}* ∧ y sufijo de x } S-> aS | bS | C C-> aCa | bCb | c R 37.
CFG no ambigua para { xcy ∣ x,y∈{a,b}* ∧ |x|=|y| ∧ |x| >0 } S-> aRb | bSa | aRa | bSb R-> aCb | bSa | aCa | bSb C-> aCb | bCa | aCa | bCb |c aa 38.
CFG para el complementario de { a b ∣ n≥0 } S -> XbaX | aA | Bb | aNb B -> bB | A -> aA | X -> aX | bX | N -> aNb | aA | bB n 39.
n CFG no ambigua para el complementario de { a b ∣ n≥0 } S-> X|Y X-> aXb | aA | Bb A-> aA | B-> bB | Y-> ABbaW n n W->aW | bW | 40.
CFG no ambigua para el complementario de { w ∈ {a,b}* ∣ w=w } S -> aYb | bYa | aSa | bSb Y -> aY | bY | R 41.
42.
CFG para el complementario de { a b c ∣ n≥0 } CFG para el complementario de { wcw ∣ w ∈ {a,b}* } S->WcWcW | T | X | AbT | BaT W->aW | bW | cW | T->aT | bT | X->YXY | YTc | cTY Y->a | b A->YAY | aTc B->YBY | bTc 43.
CFG para expresiones sobre { + , - , * , / , ( , ) , 0 , 1, …, 9 } n n n S -> M/S | M*S | M+S | M-S | M M -> (S) | N N -> 0N | 1N | 2N | 3N | 4N | 5N | 6N | 7N | 8N | 9N | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8|9 CFG no ambigua para expresiones sobre { + , - , * , / , ( , ) , 0 , 1, …, 9 } 44.
S -> M/S | M*S | M+S | M-S | M M -> (S) | N N -> 0N | 1N | 2N | 3N | 4N | 5N | 6N | 7N | 8N | 9N | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8|9 CFG para { a b c d ∣ n=m ∨ n=k ∨ n=t } 45.
n m k t S -> aMbX | aKcZ | aTd | bV | cC | dD | C -> cC | dD | D -> dD | V -> bV | Rc | Ud | R -> Rc | U -> Ud | M -> aMb | X -> cX | Zd | Z -> Zd | K -> aKc | bB | B -> bB | T -> aTd | Y | Y -> bY | cW | W -> cW | Extra: 1. CFG no ambigua per a { xcy ∣ x,y∈{a,b}* ∧ 2|x| =|y| } a b S-> BcA | BaSbAbA B-> bB | A-> Aa | CFG no ambigua per a { w ∈ {a,b}* ∣ w=w ∧ |w| =0 } 2.
R aabb S-> aXa | bRb | a | b | X-> aYa | bRb | a | b | Y-> aYa | bZb | a | b | Z-> aXa | a R-> bTb | aXa | a | b | T-> bTb | aUa | a | b | U-> bRb | b CFG no ambigua per a { a b c d ∣ i+k=j+t } 3.
i j k t S-> aSd | aXbY | bYcT | cTd | X-> aXb | Y-> bYc | T-> cTd | CFG no ambigua per a { a b ∣ j<i<2j } 4.
i j S-> aaaXbb X-> aaXb | Y Y-> aYb | 5.
CFG no ambigua per al complementari dels mots ben parentitzats sobre { [ , ],(,)} Regular Operations 1.
Regular description for { w ∈ {a,b}* ∣ |w| >0 ∨ |w| >0 ∨ |w| >0 ∨ |w| >0} aaa bbb bab main { // Escriu aqui la teva descripcio regular.
a = "a"; b = "b"; ab = a|b; // | -> unió dels llenguatges 'a' i 'b' //l'espai en blanc es una concatenacio aaa = a a a; bbb = reverse(b b b); //ravassat (o invers) aba = "aba"; //llenguatge que te aquest mot bab = b a b; //llenguatge concatenacio dels llenguatges 'b' 'a' i 'b' aba output ab* ( aaa | bbb | aba | bab) ab*; } 2.
Regular description for { w ∈ {a,b}* ∣ |w| >0 ∧ |w| >0 ∧ |w| >0 ∧ |w| >0} aaa bbb bab main { // Escriu aqui la teva descripcio regular.
a = "a"; b = "b"; ab = a|b; aaa = a a a; bbb = b b b; aba = a b a; bab = b a b; R = ab* aaa ab* & ab* bbb ab* & ab* aba ab* & ab* bab ab*; output R; } 3. Regular description for { w ∈ {a,b}* ∣ |w| =|w| =1} main { // Escriu aqui la teva descripcio regular.
a = "a"; b = "b"; ab = a|b; aaa = a a a; bbb = b b b; aaaa = a a a a; bbbb = b b b b; A = ab* aaa ab* - (ab* aaaa ab* | ab* aaa ab* aaa ab*); B = ab* bbb ab* - (ab* bbbb ab* | ab* bbb ab* bbb ab*); output A&B; } aaa bbb 4. Regular description for { w ∈ {a,b}* ∣ |w| =|w| =1} main { // Escriu aqui la teva descripcio regular.
a = "a"; b = "b"; ab = a|b; aba = a b a; bab = b a b; ababa = a b a b a; babab = b a b a b; aba bab aba ABA = ab* aba ab* - (ab* aba ab* aba ab* | ab* ababa ab*); BAB = ab* bab ab* - (ab* bab ab* bab ab* | ab* babab ab*); output ABA & BAB; } Regular description for { w ∈ {a,b}* ∣ ∃ w₁,w₂: (w=w₁aw₂ ∧ |w₂|=5) ∧ |w| >0} main { // Escriu aqui la teva descripcio regular.
a = "a"; b = "b"; ab = a|b; bbb = "bbb"; L = ab* bbb ab* a ab ab ab ab ab; L1 = ab* a bbb ab ab; L2 = ab* a ab bbb ab; L3 = ab* a ab ab bbb; 5.
bbb R = (L|L1|L2|L3); output R; } 6. (A) Regular description for { w ∈ {0,1}* ∣ value₂(w) is multiple of 12 } main { //multiples de 12 = multiples de 4 ^ multiples de 3.
//(3 i 4 coprimers, factoritzacio 12 surt 3 i 4).
3 =" 0 1 001+ 1 20 2 1 2"; 0 = "0"; 1 = "1"; 01 = 0|1; 4 = 01* 0 0 | 0 | ""; output 3&4; } 7. Regular description for { w ∈ {0,1}* ∣ value₂(w) is multiple of 20 } main { mult_4=" 0 1 0 01+ 1 23 2 01 3 2 3"; mult_5=" 0 1 0 01+ 1 23 2 40 3 12 4 3 4"; output mult_5 & mult_4; } Regular description for { w ∈ {0,1}* ∣ value₂(w) is multiple of 60 } (A) Regular description for σ(L) where L={ w ∈ {a,b}* ∣ ∃ x,y:(w=xay ∧ |y|=2)} main { a = "a"; b = "b"; ab = a|b; w = ab* a ab ab; output substitution(w, "a" -> "aba", "b" -> "bab"); } 8.
9.
and σ is the morphism defined by σ(a)=aba and σ(b)=bab 10. (A) Regular description for σ(L) where L={ w ∈ {a,b,c}* ∣ ∃ x,y:((w=xay ∨ w=xcy) ∧ |y|=1)} main { a = "a"; b = "b"; c = "c"; abc = a|b|c; w = abc* a abc | abc* c abc; output substitution(w, "a" -> "aba", "b" -> "aa", "c" -> "b"); } and σ is the morphism defined by σ(a)=aba, σ(b)=aa and σ(c)=b 11. Regular description for σ(L) where L={ w ∈ {a,b}* ∣ ∃ x,y:(w=xay ∧ |y|=2)} and σ is the substitution defined by σ(a)=(aa)* and σ(b)=(bab|aba|a) main { a = "a"; b = "b"; ab = a|b; w = ab* a ab ab; output substitution(w, "a" -> "aa"*, "b" -> "bab" | "aba" | "a"); } 12. Regular description for the language recognized by the NFA with set of states {0,1,2,3,4,5}, initial state 0, accepting state 4, and transitions δ(0,a)={1,3}, δ(0,b)=4, δ(1,a)=4, δ(1,b)={2,3}, δ(2,b)=5, δ(3,a)=2, δ(4,a)={0,5}, δ(4,b)={0,2}, δ(5,a)=4 main { nfa =" a c b d 0 134r 1 4r23 2 rr5r 3 2rrr 4 0502+ 5 4rrr r r r r r"; output substitution(nfa, "c" -> "a", "d" -> "b"); } 13. Regular description for the language recognized by the NFA with set of states {0,1,2,3,4,5}, initial states {2,5}, accepting state 4, and transitions δ(0,a)={1,3}, δ(0,b)=4, δ(1,a)=4, δ(1,b)={2,3}, δ(2,b)=5, δ(3,a)=2, δ(4,a)={0,5}, δ(4,b)={0,2}, δ(5,a)=4 main { // dos estats inicials: afegeixo simbols "e" i "f" que despres amb //substitution "e" -> "" porten als estats inicials A=" a c b d e f i rrrr25 0 134rrr 1 4r23rr 2 rr5rrr 3 2rrrrr 4 0502rr+ 5 4rrrrr r r r r r r r"; output substitution(A, "e" -> "", "f" -> "", "c" -> "a", "d" -> "b"); } 14. Regular description for {a ∣ n∈D}, where D is the set of distances of paths (with allowed repetition of nodes in the path) from node 0 to node 4 in the directed graph with edges labelled with lengths whose set of nodes is {0,1,2,3,4} and whose set of edges is {0→(4)→1, 1→(4)→2, 1→(6)→3, 2→(4)→0, 2→(2)→4, 3→(2)→0, 4→(4)→3} main { graph=" 2 4 6 0 r1r 1 r23 2 40r 3 0rr 4 r3r+ r r r r"; output substitution(graph, "2" -> "aa", "4" -> "aaaa", "6" -> "aaaaaa"); } n 15. Regular description for {a ∣ n∈D}, where D is the set of distances of paths (with allowed repetition of nodes in the path) n from node 0 to node 5 in the directed graph with edges labelled with lengths whose set of nodes is {0,1,2,3,4,5} and whose set of edges is 0→(7)→1, 0→(4)→2, 1→(7)→1, 1→(9)→3, 2→(4)→4, 2→(3)→5, 3→(4)→0, 4→(5)→2, 4→(3)→3, 5→(9)→4 main { graph=" 3 4 5 7 9 0 r2r1r 1 rrr13 2 54rrr 3 r0rrr 4 3r2rr 5 rrrr4+ r r r r r r"; output substitution(graph, "3" -> "aaa","4" -> "aaaa","5" -> "aaaaa","7" -> "aaaaaaa","9" -> "aaaaaaaaa"); } 16. Regular description for σ(L) where L={ w ∈ {a,b}* ∣ |w| is even} and σ is the transducer with states {0,1,2} and transitions 0→(a|aba)→1, 0→(b|bb)→2, 1→(a|b)→2, 1→(b|a)→0, 2→(a|a)→1, 2→(b|bbba)→0 main { // Escribe aqui tu descripcion regular.
A=" 0 1 2 3 4 5 012rrrr+ 1rr20rr+ 2rrrr10+ r r r r r r r "; B=" 0 1 2 3 4 5 0101010+ 1 0 1 0 1 0 1 "; output substitution(A&B, "0"->"aba", "1"->"bb", "2"->"b", "3"->"a", "4"->"a", "5"->"bbba"); } a v2: main { L=" ab 0 10+ 1 0 1"; L = substitution (L, "a" -> "a" | "b" | "c", "b" -> "d" | "e" | "f"); t=" abc def 0 1pp 2pp+ 1 p2p p0p+ 2 pp1 pp0+ p p p p p p p"; output substitution ( L & t, "a" -> "aba", "b" -> "b", "c" -> "a", "d" -> "bb", "e" -> "a", "f" -> "bbba"); } 17. Regular description for σ(L) where L={ xay ∈ {a,b}* ∣ |y|=1 } and σ is the transducer with states {0,1} and transitions 0→(a|aba)→0, 0→(b|b)→1, 1→(a|b)→0, 1→(b|aa)→1 18. Regular description for { intercal(w₁,w₂) ∣ w₁,w₂∈{0,1}* ∧ |w₁|=|w₂| ∧ value₂(w₁)>value₂(w₂) }, where intercal(a₁w₁,…,a w )=a₁…a intercal(w₁,…,w ) and intercal(λ,…,λ)=λ 19. Regular description for { intercal(w₁,w₂) ∣ w₁,w₂∈{0,1}* ∧ |w₁|=|w₂| ∧ value₂(w₁)<value₂(w₂) }, where intercal(a₁w₁,…,a w )=a₁…a intercal(w₁,…,w ) and intercal(λ,…,λ)=λ 20. Regular description for { intercal(w₁,w₂,w₃) ∣ w₁,w₂,w₃∈{0,1}* ∧ |w₁|=|w₂|=|w₃| ∧ value₂(w₁)>value₂(w₂)>value₂(w₃) }, where intercal(a₁w₁,…,a w )=a₁…a intercal(w₁,…,w ) and intercal(λ,…,λ)=λ main { // Escribe aqui tu descripcion regular.
A=" 0 1 2 3 igual igual menor major igual major major major major major + menor menor menor menor menor"; 0="0"; 1="1"; 01=0|1; output substitution(A, "0"->"00"01,"1"->"01"01,"2"->"10"01,"3"->"11"01) & substitution(A, "0"->01"00","1"->01"01","2"->01"10","3"->01"11"); } n n n n n n n n n n n n 21. Regular description for { intercal(w₁,w₂,w₃) ∣ w₁,w₂,w₃∈{0,1}* ∧ |w₁|=|w₂|=|w₃| ∧ value₂(w₁)>value₂(w₂)<value₂(w₃) }, where intercal(a₁w₁,…,a w )=a₁…a intercal(w₁,…,w ) and intercal(λ,…,λ)=λ 22. Regular description for { intercal(w₁,w₃) ∣ ∃ w₂: (w₁,w₂,w₃∈{0,1}* ∧ |w₁|=|w₂|=|w₃| ∧ value₂(w₁)>value₂(w₂)>value₂(w₃)) }, where intercal(a₁w₁,…,a w )=a₁…a intercal(w₁,…,w ) and intercal(λ,…,λ)=λ 23. Regular description for { intercal(w₁,w₂,w₃) ∣ w₁,w₂,w₃∈{0,1}* ∧ |w₁|=|w₂|=|w₃| ∧ value₂(w₁)+value₂(w₂)=value₂(w₃) , where intercal(a₁w₁,…,a w )=a₁…a intercal(w₁,…,w ) and intercal(λ,…,λ)=λ n n n n n n n n n n n n main { L=" // 000 001 010 011 100 101 110 111 a b c d e f g h ok ok r r ok r ok okc r + okc r ok okc r okc r r okc r r r r r r r r r "; R = reverse (L); output substitution(R, "a"->"000", "b"->"001", "c"->"010", "d"->"011", "e"->"100", "f"->"101", "g"->"110", "h"->"111"); } 24. Regular description for { intercal(w₁,w₂,w₃,w₄) ∣ w₁,w₂,w₃,w₄∈{0,1}* ∧ |w₁|=|w₂|=|w₃|=|w₄| ∧ value₂(w₁)+value₂(w₂)=value₂(w₃)>value₂(w₄) }, where intercal(a₁w₁,…,a w )=a₁…a intercal(w₁,…,w ) and intercal(λ,…,λ)=λ 25. Regular description for { intercal(w₁,w₂,w₄) ∣ ∃ w₃: (w₁,w₂,w₃,w₄∈{0,1}* ∧ |w₁|=|w₂|=|w₃|=|w₄| ∧ value₂(w₁)+value₂(w₂)=value₂(w₃)>value₂(w₄)) }, where intercal(a₁w₁,…,a w )=a₁…a intercal(w₁,…,w ) and intercal(λ,…,λ)=λ 26. Regular description for { intercal(w₁,w₂,w₄,w₅) ∣ ∃ w₃: (w₁,w₂,w₃,w₄,w₅∈{0,1}* ∧ |w₁|=|w₂|=|w₃|=|w₄|=|w₅| ∧ value₂(w₁)+value₂(w₂)=value₂(w₃)>value₂(w₄)+value₂(w₅)) }, where intercal(a₁w₁,…,a w )=a₁…a intercal(w₁,…,w ) and intercal(λ,…,λ)=λ n n n n n n n n n n n n extra 1 main { // Escriu aqui la teva descripcio regular.
a = "a"; b = "b"; ab = a|b; L = ab* a b b a ab*; L0 = ab* L ab* L ab*|ab* a b b a b b a ab*; L1 = L - L0; L2 = ab* a a a ab*; L3 = ab* b b b ab* b b b ab* |ab* b b b b ab*; output ( (L1 - L2) | (L1 & L3) ); } extra 2 main { L=" 0 1 2 3 4 5 6 7 8 9 a b c d e f ok ok r r ok r ok okc r r ok okc r okc r r okc + okc r ok okc r okc r r okc okc r r okc r okc okC r okC okc r r okc r okc okC r r okc okC r okC r r okC r r r r r r r r r r r r r r r r r "; R = reverse(L); output substitution (R, "0"->"0000", "1"->"0001", "2"->"0010", "3"->"0011", "4"->"0100", "5"->"0101", "6"->"0110", "7"->"0111", "8"->"1000", "9"->"1001", "a"->"1010", "b"->"1011", "c"->"1100", "d"->"1101", "e"->"1110", "f"->"1111"); } extra 3 main { a = "a"; b = "b"; ab = a|b; L19 = b ab ab ab ab ab ab ab b ab ab ab ab ab ab ab | a ab ab ab ab ab ab ab a ab ab ab ab ab ab ab; L210= ab b ab ab ab ab ab ab ab b ab ab ab ab ab ab | ab a ab ab ab ab ab ab ab a ab ab ab ab ab ab; L311= ab ab b ab ab ab ab ab ab ab b ab ab ab ab ab | ab ab a ab ab ab ab ab ab ab a ab ab ab ab ab; L412= ab ab ab b ab ab ab ab ab ab ab b ab ab ab ab | ab ab ab a ab ab ab ab ab ab ab a ab ab ab ab; L513= ab ab ab ab b ab ab ab ab ab ab ab b ab ab ab | ab ab ab ab a ab ab ab ab ab ab ab a ab ab ab; L614= ab ab ab ab ab b ab ab ab ab ab ab ab b ab ab | ab ab ab ab ab a ab ab ab ab ab ab ab a ab ab; L715= ab ab ab ab ab ab b ab ab ab ab ab ab ab b ab | ab ab ab ab ab ab a ab ab ab ab ab ab ab a ab; L816= ab ab ab ab ab ab ab b ab ab ab ab ab ab ab b | ab ab ab ab ab ab ab a ab ab ab ab ab ab ab a ; output L19 &L210&L311&L412&L513&L614&L715&L816; } Context-free Operations 1. Context-free description for { w ∈ {a,b}* ∣ |w| =|w| ∧ |w| >0 } main { // Write here your context-free description.
g = "S -> aXbS | bYaS | X -> aXbX | Y -> bYaY |"; output g & ("a"|"b")* "abba" ("a"|"b")*; } 2. Context-free description for { w ∈ {0,1}* ∣ w=w ∧ value₂(w) multiple of 5 } 3. Context-free description for well-parenthesised words over { ( , ) } with no occurrence of ((( main { g = "S -> (S)S |"; output g - ("("|")")* "(((" ("("|")")*; } a b abba R Context-free description for { intercal(w₁,w₂) ∣ w₁,w₂∈{a,b}* ∧ |w₁|=|w₂| ∧ w₁=w₁ ∧ |w₂| =0 }, where intercal(a₁w₁,…,a w )=a₁…a intercal(w₁,…,w ) and intercal(λ,…,λ)=λ 5. Context-free description for { intercal(w₁,w₂) ∣ w₁,w₂∈{a,b}* ∧ |w₁|=|w₂| ∧ |w₂| =0 ∧ ∀ x₁,y₁,x₂,y₂:(w₁=x₁y₁ ∧ w₂=x₂y₂ ∧ |x₁|=|x₂| ⇒ |x₁| ≥|x₂| ) }, 4.
R aa n aa a a n n n where intercal(a₁w₁,…,a w )=a₁…a intercal(w₁,…,w ) and intercal(λ,…,λ)=λ 6. Context-free description for { a b a b a b ∣ i+k+s=j+r+t } 7. Context-free description for { a b a b a b ∣ i+k+s=2(j+r+t) } 8. Context-free description for { a b a b a b ∣ i+k+r+t=j+s } 9. Context-free description for { w₁aw₂aw₃ ∣ w₁,w₂,w₃∈{0,1}* ∧ |w₁|=|w₂|₀+|w₃|₁ ∧ |w₁w₂|₁₁₁≥1 } 10. Context-free description for { a bw₁aw₂ ∣ w₁,w₂∈{a,b}* ∧ n=|w₂| ∧ |w₁w₂| =0 ∧ w₁=w₁ } 11. Context-free description for { w₁aw₂aw₃ ∣ w₁,w₂,w₃∈{0,1}* ∧ |w₁|=|w₃| ∧ value₂(w₁w₃) multiple of 12 ∧ w₂∈{0 1 |n≥0} } n n n n i j k r s t i j k r s t i j k r s t n R aaa n n PDAs 1. Deterministic uniquely-accepting PDA for { a b ∣ n≥0 } 2. Deterministic uniquely-accepting PDA for { a b ∣ n≥0 } Z ini ini final n 2n n n ini -> Za|ZA -> qa qa -> Aa|A -> qaa qaa -> Aa|AA -> qa qaa -> Ab| -> qb qb -> Ab| -> qb qb -> Z|Z -> final 3. Deterministic uniquely-accepting PDA for { w ∈ {a,b}* ∣ |w| =|w| } Z ini ini ini -> Za|ZA -> qa ini -> Zb|ZB -> qb a b // Las As se apilan y las Bs desapilan. Cuando se igualan, se vuelve al estado inicial.
qa -> Aa|AA,Ab| -> qa qa -> Z|Z -> ini // Las Bs se apilan y las As desapilan. Cuando se igualan, se vuelve al estado inicial.
qb -> Bb|BB,Ba| -> qb qb -> Z|Z -> ini 4. Deterministic uniquely-accepting PDA for { w ∈ {a,b}* ∣ |w| ≠|w| } Z ini qa qb ini -> Za|ZA -> qa ini -> Zb|ZB -> qb a b // Las As se apilan y las Bs desapilan. Cuando se igualan, se vuelve al estado inicial.
qa -> Aa|AA,Ab| -> qaa qaa -> A|A qaa -> Z|Z -> qa -> ini // Las Bs se apilan y las As desapilan. Cuando se igualan, se vuelve al estado inicial.
qb -> Bb|BB,Ba| -> qbb qbb -> B|B qbb -> Z|Z -> qb -> ini 5. Deterministic uniquely-accepting PDA for { w ∈ {a,b}* ∣ |w| ≥|w| } Z ini ini qa a b ini -> Za|ZA -> qa ini -> Zb|ZB -> qb qa -> Aa|AA -> qaa qa -> Ab| -> qaa qaa -> A|A -> qa qaa -> Z|Z -> ini qb -> Bb|BB -> qbb qb -> Ba| -> qbb qbb -> B|B -> qb qbb -> Z|Z -> ini 6. Deterministic uniquely-accepting PDA for { w ∈ {a,b}* ∣ 2|w| =|w| } // Escriu aqui el teu PDA...
a b Z in eq in -> Z|Z -> eq eq -> Za|ZAA -> as eq -> Zb|ZB -> bs as -> Aa|AAA -> as as -> Ab| -> limbo limbo -> A|A -> as limbo -> Z|Z -> eq bs -> Bb|BB -> bs bs -> Ba| -> aux aux -> B| -> limbo2 aux -> Z|ZA -> as 7. Deterministic uniquely-accepting PDA for { w ∈ {a,b}* ∣ 2|w| ≥|w| } // Escriu aqui el teu PDA...
a b Z in eq as in -> Z|Z -> eq eq -> Za|ZAA -> as eq -> Zb|ZB -> bs as -> Aa|AAA -> as as -> Ab| -> limbo limbo -> Z|Z -> eq limbo -> A|A -> as bs -> Bb|BB -> bs bs -> Ba| -> aux aux -> B| -> limbo2 aux -> Z|ZA -> as limbo2 -> Z|Z -> eq limbo2 -> B|B -> bs 8. Deterministic uniquely-accepting PDA for { w ∈ {a,b}* ∣ 2|w| ≤|w| } // Escriu aqui el teu PDA...
a b Z in eq bs in -> Z|Z -> eq eq -> Za|ZAA -> as eq -> Zb|ZB -> bs as -> Aa|AAA -> as as -> Ab| -> limbo limbo -> A|A -> as limbo -> Z|Z -> eq bs -> Bb|BB -> bs bs -> Ba| -> aux aux -> B| -> limbo2 aux -> Z|ZA -> as 9. Uniquely-accepting PDA for { a b ∣ j≤i≤2j } 10. Deterministic uniquely-accepting PDA for { w ∈ {a,b}* ∣ |w| =|w| } 11. Deterministic uniquely-accepting PDA for { a b c ∣ i=j+k } ZIIF I -> Za|ZA -> A A -> Za|ZA,Aa|AA -> A A -> Zb|,Ab| -> B i j aa i j k b A -> Zc|,Ac| -> C B -> Ab| -> B B -> Ac| -> C B -> Z|Z -> F C -> Z|Z -> F C -> Ab| -> POU C -> Ac| -> C F -> Zb| -> POU F -> Zc| -> POU Solució millor: ZIIF I -> Za|ZA -> A A -> Za|ZA,Aa|AA -> A A -> Ab| -> B A -> Ac| -> C B -> Ab| -> B B -> Ac| -> C B -> Z|Z -> F C -> Z|Z -> F C -> Ac| -> C C -> Ab| -> POU 12. Deterministic uniquely-accepting PDA for { a b c ∣ j=i+k } i j k Z q0 q0 q7 q6 Z q0 -> Z q1 Z q1 a -> ZA q2 Z q1 b -> ZB q4 Z q1 c -> Z f A q2 a -> AA q2 A q2 b -> q3 A q2 c -> Z f A q3 a -> Z f A q3 b -> q3 A q3 c -> Z f Z q3 -> Z q7 Z q7 a -> Z f Z q7 b -> ZB q4 Z q7 c -> Z f B q4 a -> Z f B q4 b -> BB q4 B q4 c -> q5 B q5 c -> q5 Z q5 -> q6 Z q6 c -> Z f Z f -> Z f 13. PDA for { a b c ∣ i=j ∨ i=k } 14. PDA for { a b c ∣ i=j ∨ j=k } 15. Uniquely-accepting PDA for { a b c d ∣ i=j } ∪ {a b c e ∣ j=k } 16. Uniquely-accepting PDA for { w ∈ {a,b}* ∣ w=w } i j k i j k i j k i R j k 17. Deterministic uniquely-accepting PDA for well-parenthesised words over { ( , ) } 18. Deterministic uniquely-accepting PDA for well-parenthesised words over { [ , ] , ( , ) } 19. Deterministic uniquely-accepting PDA for { xcy ∣ x,y∈{a,b}* ∧ |x| =|y| } 20. Deterministic uniquely-accepting PDA for { xcy ∣ x,y∈{a,b}* ∧ |x| =|y| } 21. Deterministic uniquely-accepting PDA for { xcy ∣ x,y∈{a,b}* ∧ |x| =|y| } a ab aba b ba bab Problemas extra de PDAs 1. PDA determinista y de aceptacion unica para { w ∈ {a,b}* ∣ 3|w|a=|w|b } Z ini eq ini -> Z|Z -> eq eq -> Za|ZAAA -> as eq -> Zb|ZB -> bs as -> Aa|AAAA -> as as -> Ab| -> limbo limbo -> A|A -> as limbo -> Z|Z -> eq bs -> Bb|BB -> bs bs -> Ba| -> dto dto -> B| -> dto2 dto -> Z|ZAA -> as dto2 -> B| -> limbo2 dto2 -> Z|ZA -> as limbo2 -> B|B -> bs limbo2 -> Z|Z -> eq Problemes de Word Reachability 1. {⟨u,v,R⟩ ∣ Σ={a,b} ∧ u→ *v} ≤ {⟨u,v,R⟩ ∣ |Σ|≤2 ∧ u→ *v ∧ |R| even (as a list, i.e. counting repetitions)} (morphism not allowed in the reduction) R R u v l->r l->r 2.
{⟨u,v,R⟩ ∣ Σ={a,b} ∧ u→ *v} ≤ {⟨u,v,R⟩ ∣ |Σ|≤2 ∧ u→ *v ∧ |R| odd (as a list, i.e. counting repetitions)} (morphism not allowed in the reduction) u v R R l->r l->r u->u 3.
{⟨u,v,R⟩ ∣ Σ={a,b} ∧ u→ *v} ≤ {⟨u,v,R⟩ ∣ u→ *v ∧ |R| even (as a set, i.e.
not counting repetitions)} (morphism not allowed in the reduction) R R 4.
{⟨u,v,R⟩ ∣ Σ={a,b} ∧ u→ *v} ≤ {⟨u,v,R⟩ ∣ u→ *v ∧ |R| odd (as a set, i.e. not counting repetitions)} (morphism not allowed in the reduction) R R 5.
{⟨u,v,R⟩ ∣ Σ={a,b} ∧ u→ *v} ≤ {⟨u,v,R⟩ ∣ |Σ|≤3 ∧ u→ *v ∧ |R| even (as a set, i.e. not counting repetitions)} (morphism not allowed in the reduction) R R 6.
{⟨u,v,R⟩ ∣ Σ={a,b} ∧ u→ *v} ≤ {⟨u,v,R⟩ ∣ |Σ|≤3 ∧ u→ *v ∧ |R| odd (as a set, i.e. not counting repetitions)} (morphism not allowed in the reduction) R R 7.
{⟨u,v,R⟩ ∣ Σ={a,b} ∧ u→ *v} ≤ {⟨u,v,R⟩ ∣ |Σ|≤2 ∧ u→ *v ∧ |R| even (as a set, i.e. not counting repetitions)} R R 8.
{⟨u,v,R⟩ ∣ Σ={a,b} ∧ u→ *v} ≤ {⟨u,v,R⟩ ∣ |Σ|≤2 ∧ u→ *v ∧ |R| odd (as a set, i.e. not counting repetitions)} R R 9.
{⟨u,v,R⟩ ∣ Σ={a,b} ∧ u→ *v} ≤ {⟨u,v,R⟩ ∣ |Σ|≤2 ∧ u→ *v with an even number of steps} (morphism not allowed in the reduction) u v l->r v->v R R 10.
{⟨u,v,R⟩ ∣ Σ={a,b} ∧ u→ *v} ≤ {⟨u,v,R⟩ ∣ |Σ|≤2 ∧ u→ *v with an odd number of steps} (morphism not allowed in the reduction) u v l->r v->v R R 11.
{⟨u,v,R⟩ ∣ Σ={a,b} ∧ u→ *v} ≤ {⟨u,v,R⟩ ∣ u→ *v with an even number of steps but not with an odd number of steps} (morphism not allowed in the reduction) 12.
{⟨u,v,R⟩ ∣ Σ={a,b} ∧ u→ *v} ≤ {⟨u,v,R⟩ ∣ u→ *v with an odd number of steps but not with an even number of steps} (morphism not allowed in the reduction) 13.
{⟨u,v,R⟩ ∣ Σ={a,b} ∧ u→ *v} ≤ {⟨u,v,R⟩ ∣ |Σ|≤3 ∧ u→ *v with an even number of steps but not with an odd number of steps} (morphism not allowed in the reduction) 14.
{⟨u,v,R⟩ ∣ Σ={a,b} ∧ u→ *v} ≤ {⟨u,v,R⟩ ∣ |Σ|≤3 ∧ u→ *v with an odd number of steps but not with an even number of steps} (morphism not allowed in the reduction) 15.
{⟨u,v,R⟩ ∣ Σ={a,b} ∧ u→ *v} ≤ {⟨u,v,R⟩ ∣ |Σ|≤3 ∧ u→ v} (morphism not allowed in the reduction) # v l->r R R R R R R R R R + R #->u 16.
{⟨u,v,R⟩ ∣ Σ={a,b} ∧ u→ *v} ≤ {⟨u,v,R⟩ ∣ |Σ|≤2 ∧ u→ v} (morphism not allowed in the reduction) u v l->r u->u + R R 17.
{⟨u,v,R⟩ ∣ Σ={a,b} ∧ u→ *v} ≤ {⟨u,v,w,R⟩ ∣ |Σ|≤3 ∧ u→ *v→ *w} (morphism not allowed in the reduction) R R R u v # l->r v-># 18.
{⟨u,v,R⟩ ∣ Σ={a,b} ∧ u→ *v} ≤ {⟨u,v,w,R⟩ not allowed in the reduction) 19.
{⟨u,v,R⟩ ∣ Σ={a,b} ∧ u→ *v} ≤ {⟨u,v,w,R⟩ (morphism not allowed in the reduction) 20.
{⟨u,v,R⟩ ∣ Σ={a,b} ∧ u→ *v} ≤ {⟨u,v,w,R⟩ (morphism not allowed in the reduction) 21.
{⟨u,v,R⟩ ∣ Σ={a,b} ∧ u→ *v} ≤ {⟨u,v,w,R⟩ 22.
{⟨u,v,R⟩ ∣ Σ={a,b} ∧ u→ *v} ≤ {⟨u,v,R⟩ ∣ allowed in the reduction) #u# #v# l->r #v#->#v##v# R ∣ |Σ|≤2 ∧ u→ *v→ *w} (morphism R ∣ |Σ|≤4 ∧ u→ *v→ *w ∧ u≠v≠w} R ∣ |Σ|≤3 ∧ u→ *v→ *w ∧ u≠v≠w} R R 23.
{⟨u,v,R⟩ ∣ Σ={a,b} ∧ u→ *v} ≤ {⟨u,v,R⟩ allowed in the reduction) 24.
{⟨u,v,R⟩ ∣ Σ={a,b} ∧ u→ *v} ≤ {⟨u,v,R⟩ allowed in the reduction) 25.
{⟨u,v,R⟩ ∣ Σ={a,b} ∧ u→ *v} ≤ {⟨u,v,R⟩ allowed in the reduction) 26.
{⟨u,v,R⟩ ∣ Σ={a,b} ∧ u→ *v} ≤ {⟨u,v,R⟩ (morphism not allowed in the reduction) #u# #v# l->r #v#->#v##v# R R R R R R ∣ |Σ|≤2 ∧ u→ *v→ *w ∧ u≠v≠w} |Σ|≤3 ∧ u→ *vv} (morphism not R R R R ∣ |Σ|≤3 ∧ uu→ *v} (morphism not R ∣ |Σ|≤4 ∧ uu→ *vv} (morphism not R ∣ |Σ|≤3 ∧ uu→ *vv} (morphism not R ∣ |Σ|≤3 ∧ u→ *v ∧ v→ *u} R R R R R 27.
{⟨u,v,R⟩ ∣ Σ={a,b} ∧ u→ *v} ≤ {⟨u,R⟩ ∣ |Σ|≤4 ∧ u→ u} (morphism not allowed in the reduction) 28.
{⟨u,v,R⟩ ∣ Σ={a,b} ∧ u→ *v} ≤ {⟨u,R⟩ ∣ |Σ|≤3 ∧ u→ u} (morphism not allowed in the reduction) R + R R + R Problemes de reduccions de CFGs 1. (A) {⟨G₁,G₂⟩ ∣ Σ={a,b} ∧ ℒ(G₁)∩ℒ(G₂)≠∅} ≤ {⟨G₁,G₂,G₃⟩ ∣ ℒ(G₁)∩ℒ(G₂)≠∅ ∧ ℒ(G₁)∩ℒ(G₃)≠∅ ∧ ℒ(G₂)∩ℒ(G₃)≠∅} input g1,g2 { // Write your reduction here...
g1 = substitution(g1, "a"->"aa", "b"->"bb"); g2 = substitution(g2, "a"->"aa", "b"->"bb"); output g1|"a", g2|"b", "a"|"b" ; } 2.
(A) {⟨G₁,G₂⟩ ∣ Σ={a,b} ∧ ℒ(G₁)∩ℒ(G₂)≠∅} ≤ {⟨G₁,G₂,G₃⟩ ∣ ℒ(G₁)∩ℒ(G₂)≠∅ ∧ ℒ(G₂)∩ℒ(G₃)≠∅ ∧ ℒ(G₁)∩ℒ(G₃)=∅} input g1,g2 { // Escriu aqui la teva reduccio...
g1 = substitution (g1, "b"->"c"); g2 = substitution (g2, "b"->"c"); output g1 , g2 | "b" , "b" ; } 3.
(A) {⟨G₁,G₂⟩ ∣ Σ={a,b} ∧ ℒ(G₁)∩ℒ(G₂)≠∅} ≤ {⟨G₁,G₂,G₃⟩ ∣ Σ={a,b} ∧ ℒ(G₁)∩ℒ(G₂)≠∅ ∧ ℒ(G₂)∩ℒ(G₃)≠∅ ∧ ℒ(G₁)∩ℒ(G₃)=∅} input g1,g2 { // Escriu aqui la teva reduccio...
g1 = substitution (g1, "b"->"bb"); g2 = substitution (g2, "b"->"bb"); output g1 , g2 | "b" , "b" ; } 4.
{⟨G₁,G₂⟩ ∣ Σ={a,b} ∧ ℒ(G₁)∩ℒ(G₂)≠∅} ≤ {⟨G₁,G₂,G₃,G₄⟩ ∣ ℒ(G₁)∩ℒ(G₂)≠∅ ∧ ℒ(G₃)∩ℒ(G₄)≠∅ ∧ ℒ(G₁)∩ℒ(G₄)=∅ ∧ ℒ(G₂)∩ℒ(G₃)=∅} 5.
{⟨G₁,G₂⟩ ∣ Σ={a,b} ∧ ℒ(G₁)∩ℒ(G₂)≠∅} ≤ {⟨G₁,G₂,G₃,G₄⟩ ∣ Σ={a,b} ∧ ℒ(G₁)∩ℒ(G₂)≠∅ ∧ ℒ(G₃)∩ℒ(G₄)≠∅ ∧ ℒ(G₁)∩ℒ(G₄)=∅ ∧ ℒ(G₂)∩ℒ(G₃)=∅} 6.
(R) {⟨G₁,G₂⟩ ∣ Σ={a,b} ∧ ℒ(G₁)∩ℒ(G₂)≠∅} ≤ {⟨G₁,G₂⟩ ∣ |ℒ(G₁)∩ℒ(G₂)|≥2} 7.
{⟨G₁,G₂⟩ ∣ Σ={a,b} ∧ ℒ(G₁)∩ℒ(G₂)≠∅} ≤ {⟨G₁,G₂⟩ ∣ Σ={a,b} ∧ |ℒ(G₁)∩ℒ(G₂)|≥2} 8.
(A) {G ∣ ℒ(G)={a,b}*} ≤ {G ∣ ℒ(G)={a,b,c}*} input g { // Escriu aqui la teva reduccio...
a = "a"; b = "b"; c = "c"; ab = a|b; abc = a|b|c; output g c* | abc* - ab* c* ; } 9.
(A) {G ∣ ℒ(G)={a,b}*} ≤ {⟨G₁,G₂⟩ ∣ ℒ(G₁)=ℒ(G₂)} input g { // Escriu aqui la teva reduccio...
a = "a"; b = "b"; ab = a|b; output g , ab* ; } 10.
(A) {G ∣ ℒ(G)={a,b}*} ≤ {⟨G₁,G₂⟩ ∣ ℒ(G₁)⊆ℒ(G₂)} input g { // Escriu aqui la teva reduccio...
a = "a"; b = "b"; ab = a|b; output ab*, g; } 11.
(A) {⟨G₁,G₂⟩ ∣ Σ={a,b} ∧ ℒ(G₁)∩ℒ(G₂)=∅} ≤ {⟨G₁,G₂⟩ ∣ ℒ(G₁)⊆ℒ(G₂)} input g1,g2 { // Escriu aqui la teva reduccio...
output g1, g2; } 12.
(A) {G ∣ ℒ(G)={a,b}*} ≤ {⟨G₁,G₂⟩ ∣ ¬ℒ(G₁)⊆ℒ(G₂)} input g { // Escriu aqui la teva reduccio...
a = "a"; b = "b"; c = "c"; ab = a|b; abc = a|b|c; output abc* -ab* , g ; } 13.
{G ∣ ℒ(G)={a,b}*} ≤ {⟨G₁,G₂⟩ ∣ ℒ(G₁)⊆ℒ(G₂)} 14.
(A) {G ∣ ℒ(G)={a,b}*} ≤ {G ∣ ℒ(G)={wa ∣ w∈{a,b}*}} input g { // Escriu aqui la teva reduccio...
//el nostre result. fa totes les paraules acabades en a sins g genera totes les paraules output g "a" ; } 15.
(A) {G ∣ ℒ(G)={a,b}*} ≤ {G ∣ ℒ(G)={waa ∣ w∈{a,b}*}} input g { // Escriu aqui la teva reduccio...
output g "aa"; } 16.
(R) {G ∣ ℒ(G)={a,b}*} ≤ {G ∣ ℒ(G)={a,b}*-{λ}} 17.
(R) {G ∣ ℒ(G)={a,b}*} ≤ {G ∣ ℒ(G)={a,b}*-{a}} 18.
{G ∣ ℒ(G)={a,b}*} ≤ {G ∣ ℒ(G)={a,b}*-{ab}} 19.
(A) {G ∣ ℒ(G)={a,b}*} ≤ {G ∣ ℒ(G)={w∈{a,b}* ∣ |w| ≥1}} input g { // Escriu aqui la teva reduccio...
a = "a"; b = "b"; ab = a|b; output g "a" | (ab* a ab* - ab* a); } 20.
(A) {G ∣ ℒ(G)={a,b}*} ≤ {G ∣ ℒ(G)={w∈{a,b}* ∣ |w| ≥1}} input g { // Escriu aqui la teva reduccio...
a = "a"; b = "b"; ab = a|b; aa = a a; output g aa | (ab* aa ab* - ab* aa); } 21.
{G ∣ ℒ(G)={a,b}*} ≤ {G ∣ ℒ(G)={w∈{a,b}* ∣ |w| =|w| }} 22.
{G ∣ ℒ(G)={a,b}*} ≤ {G ∣ ℒ(G)={w∈{a,b}* ∣ |w| ≠|w| }} 23.
{G ∣ ℒ(G)={a,b}*} ≤ {G ∣ ℒ(G)={w∈{0,1}* ∣ valor₂(w) multiple de 3}} 24.
{G ∣ ℒ(G)={a,b}*} ≤ {G ∣ ℒ(G)={w∈{0,1}* ∣ valor₂(w) multiple de 3 mes 1}} 25.
{G ∣ ℒ(G)={a,b}*} ≤ {G ∣ ℒ(G)={w∈{0,1}* ∣ valor₂(w) multiple de 3 mes 2}} a aa a b a b ...