Lista de Exercícios - Teoria dos Conjuntos

Prévia do material em texto

Universidade Estadual da Para´ıba
Curso: Bac. em Cieˆncias da Computac¸a˜o
Componente Curricular: Ling. Formais e Teoria da computac¸a˜o
Professor: Edson Holanda
Teoria dos conjuntos - Func¸o˜es
Exerc´ıcio 1. Determine se as proposic¸o˜es sa˜o verdadeiras ou falsas:
a) { } ∈ { }
b) { } ⊆ { }
c) { } ∈ { { } }
d) { 2, 3 } ∈ { 2, 3, { 2, 4 } }
e) { a, d } ⊆ 2{a,c,{a,d}}
Exerc´ıcio 2. Liste os elementos dos conjuntos abaixo:
a) ( { a, b, c, d } ∪ { a, e }) ∩ { b, d, f }
b)
⋃ { { 1 }, { 1, 5, 9 } , ⋂ { { 7, 11 }, {7, 13 } } }
Exerc´ıcio 3. Seja M = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 }. Responda:
a) Determine uma partic¸a˜o de M com 3 elementos?
Exerc´ıcio 4. Escrever explicitamente os elementos do seguinte produto cartesiano:
a) { a , b } × { 1, 2, 3 } × { x, y }
Exerc´ıcio 5. Seja R1 = { ( 1, 1 ), ( 1, 4) , ( 3, 1), ( 3, 2 ) } em A = { 1, 2, 3, 4, 5 }.
i) R1 e´ reflexiva?
ii) R1 e´ sime´trica?
iii) R1 e´ anti-sime´trica?
iv) R1 e´ transitiva?
v) R1 e´ func¸a˜o?
1
Conceitos Ba´sicos de Linguagens
Exerc´ıcio 6. Deˆ todos os prefixos, sufixos e subpalavras de cada uma das seguintes palavras:
a) aab
b) 1100
Exerc´ıcio 7. Dado o alfabeto abaixo, determine:
Σ = { a, b, c }
a) Σ3
b) Σ∗
c) Σ+
d) uma palavra com prefixo ’ab’
Exerc´ıcio 8. Sejam Σ = { 0, 1 }, w = 10 e v = 111. determine:
a) vw2
b) 02
c) vwv
d) (wv)2
Autoˆmatos Finitos Determin´ısticos - AFD
Exerc´ıcio 9. Deˆ a representac¸a˜o em diagrama de transic¸o˜es e em tabela de transic¸o˜es, para o
Autoˆmato Finito Determin´ıstico (AFD) abaixo:
a) M1 = (Σ, Q, δ, q0, F ), no qual:
Σ = {a, b} Q = {q0, q1, q2, q3}
δ(q0, a) = q1 δ(q0, b) = q3
δ(q1, a) = q2 δ(q1, b) = q3
δ(q2, a) = q2 δ(q2, b) = q2
δ(q3, a) = q3 δ(q3, b) = q3
2
q0 = estado inicial
F = {q2}
Exerc´ıcio 10. Mostre, usando a func¸a˜o de transic¸a˜o estendida, se as strings abaixo sa˜o aceitas, ou
na˜o, pelos autoˆmatos da questa˜o anterior:
a) ab
b) bab
c) aabb
Exerc´ıcio 11. Deˆ a representac¸a˜o em diagrama de transic¸o˜es e em tabela de transic¸o˜es, para os
autoˆmatos finitos determin´ısticos (AFD) cujo conjunto de s´ımbolos de entrada e´ Σ = { 0, 1 } e que aceite
todas, e somente, as strings que:
a) tenham como prefixo ‘00’;
b) tenham como sufixo ‘11’;
c) tenham como subpalavra ‘01’.
Exerc´ıcio 12. Mostre, usando a func¸a˜o de transic¸a˜o estendida, se as strings abaixo sa˜o aceitas, ou
na˜o, pelos autoˆmatos da questa˜o anterior:
a) 10
b) 111
c) 1101
Autoˆmatos Finitos Na˜o-Determin´ısticos - AFN
Exerc´ıcio 13. Construa um Autoˆmato Finito Na˜o-deterministico (AFN) A1 cujo conjunto de
s´ımbolos de entrada e´ Σ = { a , b, c } e que aceite todas, e somente, as strings que:
a) tenham como prefixo ‘aa’;
3
b) tenham como sufixo ‘bb’;
c) tenham como subpalavra ‘ac’.
d) tenham como sufixo ’aa’ ou ’cc’ .
Exerc´ıcio 14. Mostre, usando a Func¸a˜o de Transic¸a˜o Estendida, se as strings abaixo sa˜o aceitas, ou
na˜o, pelo autoˆmato da questa˜o anterior:
a) aab
b) acc
Exerc´ıcio 15. Encontre um Autoˆmato Finito Determin´ıstico (AFD) A2 equivalente ao da questa˜o
anterior.
Autoˆmatos Finitos com Movimentos Vazios - AFε
Exerc´ıcio 16. Construa um autoˆmato finito com movimentos vazios (AFε) A1 que aceite a seguinte
linguagem:
a) Um AFε cujo conjunto de s´ımbolos de entrada e´ Σ = { a , b, c } e que aceite todas e somente as
strings que tenham ”ab ou ”cb”como prefixo.
Exerc´ıcio 17. Mostre, usando a Func¸a˜o de Programa (de Transic¸a˜o) Estendida, se as strings abaixo sa˜o
aceitas, ou na˜o, pelo autoˆmato da questa˜o anterior:
a) ab
b) acb
c) cbbb
4
Exerc´ıcio 18. Encontro o Autoˆmato Finito Determin´ıstico equivalente, ao autoˆmato da 1a Questa˜o
Expresso˜es Regulares
Exerc´ıcio 19. Fornec¸a descric¸o˜es em portugueˆs das linguagens correspondentes a`s seguintes expresso˜es
regulares:
a) bb(a+b+c)*
b) (0+1)*11
c) (a + b + c)*(aa + b + ccc)
d) (a+b)*aba(a+b)*
e) (a + b)*c(a + b)*
f) (a + b + c)*b(a + b + c)*
Exerc´ıcio 20. Escreva Expresso˜es Regulares correspondentes a`s seguintes linguagens:
a) O conjunto de strings sobre o alfabeto { a, b, c } que conteˆm ”aaa”como prefixo e ”cc”como sufixo.
b) O conjunto de strings sobre o alfabeto { a, b, c } que conteˆm pelo menos um ”a”.
c) O conjunto de strings sobre o alfabeto Σ = { 0, 1 } que consiste de 0´s e 1´s alternados;
Exerc´ıcio 21. Aplique o algoritmo de traduc¸a˜o de Expressa˜o Regular para Autoˆmato Finito:
a) a
b) ba
c) b + c
d) a + ε
e) a*
f) (a + b) + a
g) (ε+ a)a
h) a*(b + c)
i) (a + b)(bb)*a
j) aa(b + a)*b
Grama´ticas
5
Exerc´ıcio 22. Dada a grama´tica G1 abaixo, mostre utilizando derivac¸o˜es que os itens abaixo, pertencem
a L(G1).
G1 = ( V , T , P , S )
V = { S , A , B }
T = { a , b }
P = { S → aS | A ,
A → bA | B,
B → cB | ε }
a) aaab
b) abbccc
Exerc´ıcio 23. Dada a grama´tica G2 que gera expresso˜es aritme´ticas com pareˆnteses balanceados, dois
operadores (+ e *) e dois operandos x e y, mostre utilizando derivac¸o˜es que os itens abaixo, pertencem a
L(G2).
G2 = ( V , T , P , E )
V = { E }
T = { x , y, +, *, ( , ) }
P = { E → x | y | ( E ) | E + E | E * E }
a) ( x + y )
b) ( ( y * x ) + y )
Grama´ticas Regulares
Exerc´ıcio 24. Dada a grama´tica GLD abaixo, encontre as grama´ticas lineares GLE, GLUD e GLUE e
depois deˆ a expressa˜o regular que gere a mesma linguagem:
G2 = ( V , T , P , S )
V = { S, A }
T = { a , b }
P = { S → aS | bS | A ,
A → aa | bb }
6
Exerc´ıcio 25. Encontre grama´ticas GLD que gerem as mesmas linguagens denotadas pelas expresso˜es
regulares abaixo:
a) (a + b)(ccc)*d
b) (bb + c)*(aa + d)*
Grama´ticas - Traduc¸o˜es e Derivac¸o˜es
Exerc´ıcio 26. Dada a grama´ticaG1 abaixo. Encontre o AFN equivalente (utilizando o algoritmo estudado
em sala).
G1 = ( V , T , P , S )
V = { S , A , B }
T = { a , b }
P = { S → aS | A ,
A → bA | B,
B → cB | ε }
Exerc´ıcio 27. Dada a grama´tica G2 abaixo, construa a a´rvore de derivac¸a˜o para as strings abaixo:
G1 = ( V , T , P , E )
V = { E }
T = { x , y, +, *, ( , ) }
P = { E → x | y | ( E ) | E + E | E * E }
a) ((x) + y * x )
b) ((x) * (x + y))
Exerc´ıcio 28. Considera a grama´tica G2 acima. Escreva uma derivac¸a˜o mais a esquerda e uma derivac¸a˜o
mais a direita para as strings abaixo:
a) ( x + y )
b) (((x) * x) + y)
7
Autoˆmatos com Pilha - APN
Exerc´ıcio 29. Existem dois modelos equivalentes para autoˆmatos com pilha. Explique as diferenc¸as entre
eles.
Exerc´ıcio 30. O que representa o func¸a˜o de transic¸a˜o para autoˆmato com pilha abaixo:
δ(q2, ?, a) = (q1, b)
Exerc´ıcio 31. Deˆ a representac¸a˜o em diagrama de transic¸o˜es para o autoˆmato com pilha abaixo:
M1 = ( { a, b}, { q0, q1, qf }, δ1, q0, { qf }, { a, b })
δ1(q0, a, ε) = (q0, a)
δ1(q0, b, ε) = (q0, b)
δ1(q0, ε, ε) = (q1, ε)
δ1(q1, a, a) = (q1, ε)
δ1(q1, b, b) = (q1, ε)
δ1(q1, ?, ?) = (qf , ε)
Exerc´ıcio 32. Dadas as strings abaixo, quais sa˜o aceitas e quais sa˜o rejeitadas pelo APN da questa˜o
anterior? Justifique mostrando o processamento do APN para cada string.
a) aab
b) baab
c) bbbb
8
Programas e Ma´quinvas
Exerc´ıcio 33. Escreva um programa monol´ıtico que corresponda a cada fluxograma abaixo:
a)
Partida
F1
T1
F2
F3
F4
Parada
V
F
9
b)
Partida
F1
T1 F2 F3
F4
F5T2Parada
F6
V
FV
F
Exerc´ıcio 34. Encontre programas iterativos e recursivos equivalentes aos programas monol´ıticos da
primeira questa˜o.
Exerc´ıcio 35. Escreva um programa monol´ıtico que execute as func¸o˜es F1, F2 e F3 enquanto o teste T
seja verdadeiro e depois execute F4.
Exerc´ıcio 36. Escreva um programa iterativo que execute as operac¸o˜es F2 e F4, depois execute as
operac¸o˜es F1, F2 e F3 ate´ que o teste T seja verdadeiro. Em seguida, execute as operac¸o˜es F4,F5 e F2.
10
Exerc´ıcio 37. Dados o programa e a entrada abaixo, fac¸a a computac¸a˜o para a ma´quina de dois regis-
tradores:
a) Programa P1 = ( I1 , 1)
I1 = { 1: se a-zero enta˜o va´-para 6 sena˜o va´-para 2
2: fac¸a subtrai-a va´-para 3
3: fac¸a adiciona-b va´-para 4
4: fac¸a adiciona-b va´-para 5
5: fac¸a adiciona-b va´-para 1 }
entrada: (3)
b) Programa: P2 e´ R1 onde
R1 def (se a-zero enta˜o Xsena˜o R2),
R2 def subtrai-a;R3;
R3 def adiciona-b;adiciona-b;R1;
Entrada (2)
Exerc´ıcio 38. Dados o programa e a entrada abaixo, fac¸a a computac¸a˜o para a ma´quina de um registrador
um-reg:
b) Programa prog-reg e´ R1 onde
R1 def (se zero enta˜o Xsena˜o R2);
R2 def sub;R1;
Entrada (3)
Exerc´ıcio 39. Qual a func¸a˜o computada pelo programa da questa˜o anterior, na ma´quina um-reg
f(x) =
Grama´ticas Sens´ıveis ao Contexto
11
Exerc´ıcio 40. Defina ”Linguagem Sens´ıvel ao contexto”.
Exerc´ıcio 41. Qual restric¸a˜o existia nas grama´ticas livres do contexto que na˜o existe mais nas grama´ticas
sens´ıveis ao contexto?
Exerc´ıcio 42. Dada a grama´tica G1 (sens´ıvel ao contexto) abaixo:
G1 = ({S,B,C},{a,b,c},P,S), com
P = {S → aSBC | aBC,
CB → BC,
aB → ab,
bB → bb,
bC → bc,
cC → cc }
Encontre derivac¸o˜es para as seguintes strings:
a) abc
b) aabbcc
Exerc´ıcio 43. A string ”aabc”pode ser gerada pela grama´tica G1 da questa˜o anterior?
Ma´quina Norma
Exerc´ıcio 44. Desenvolva um programa, em ma´quina Norma, que realize as operac¸o˜es abaixo:
a) B := B2
b) A:= A x B usando C (que preserva o valor de B)
c) B:= C + 4 (que preserva os valores de C)
d) A := B2 + 1 (que preserva o valor de B)
e) A:= B x C + 1 (que preserva o valor de B)
12
Operac¸o˜es ba´sicas:
A:= A – 1 Teste: A = 0
A:= A + 1
A:= 0
Exerc´ıcio 45. Determine qual a func¸a˜o computada, pelo programa abaixo, em uma Ma´quina Norma:
D:= C usando E;
A : = 0
ate´ ( D = 0 )
fac¸a (A := A + B usando E;
D := D - 1);
Ma´quinas de Turing
Exerc´ıcio 46. Cite 2 formalismo com o mesmo poder computacional de uma ma´quina de Turing.
Exerc´ıcio 47. Cite uma evideˆncia interna de que um formalismo e´ uma ma´quina universal.
Exerc´ıcio 48. Quais os 3 componentes ba´sicos de uma ma´quina de Turing?
Exerc´ıcio 49. Qual a configurac¸a˜o inicial da fita em uma ma´quina de Turing?
Exerc´ıcio 50. Quais as condic¸o˜es de parada de uma ma´quina de Turing?
13
Exerc´ıcio 51. Dado a Ma´quina de Turing MT1, mostre que as palabras abaixo sa˜o aceitas ou na˜o por
MT1:
MT1 = ({a, b}, {q0, q1, q2, q3, q4},Π, q0, {q4}, {A,B}, β,B), no qual
a) aaabbb
b) aabbba
Exerc´ıcio 52. Dado a Ma´quina de Turing MT2, que computa a func¸a˜o conc(), calcule:
MT2 = ({a, b,#}, {q0, q1, q2, q3, q4},Π, q0, {q4}, {}, β,B), no qual
a) conc(abb,aab)
b) conc(aab,ba)
Exerc´ıcio 53. Dada a hierarquia de ma´quinas estudado em sala, qual ma´quina corresponde a` uma
linguagen recursiva?
Exerc´ıcio 54. Por que a tese de Church na˜o pode ser demonstrada?
14
Exerc´ıcio 55. Defina ”Linguagem Enumera´vel Recursivamente”.
Exerc´ıcio 56. Em termos de uma ma´quina de Turing, qual a diferenc¸a entre uma linguagem Recursiva
e uma linguagem Enumera´vel Recursivamente?
Func¸o˜es Recursivas
Exerc´ıcio 57. Qual a diferenc¸a entre uma func¸a˜o parcial e uma func¸a˜o total?
Exerc´ıcio 58. Defina ”funcional”.
Exerc´ıcio 59. Deˆ um exemplo de funcional, que receba 3 argumentos.
Exerc´ıcio 60. Suponha que x, y e z tenham seus valores em N e que o tipo da func¸a˜o g e´ g : N2 → N.
Para cada item abaixo, determine o tipo da func¸a˜o f .
a) f(x, y) = x2 + y2
b) f(x, y, z) = x + y + z
c) f(x, y, g) = g( x, y)
d) f(x, g) = (g(x, x), x2)
Exerc´ıcio 61. Fac¸a as ”reduc¸o˜es beta”poss´ıveis nas termos lambda abaixo:
a) (λy.(λx.5y + x2 + xz) (3) ) (1)
15
b) (λy.y + 4) ((λx.2x+ z) (2) )
c) (λz.(λy.(λx.x+ y3 + zx) (5) (3) ) (2)
Exerc´ıcio 62. Nos termos lambda abaixo, quais varia´veis esta˜o livres? Quais esta˜o ligadas?
a) (λx.λz.xy + z)(z)
b) (λx.λy.z2 + x+ 2y)λz.x+ 2z)
c) (λx.λz.(z2 + x+ 2y))(z)
Exerc´ıcio 63. Dadas as func¸o˜es h(x, y, z) : N3 → N, g(x, y) : N2 → N, f1(x, y, z) : N3 → N e f2(x, y, z) :
N3 → N. Mostre como poderia ser definida a func¸a˜o h constru´ıda como a composic¸a˜o das func¸o˜es g, f1 e
f2 acima.
Exerc´ıcio 64. Usando as func¸o˜es zero(x) e suc(x) e a composic¸a˜o de func¸o˜es, construa uma func¸a˜o
quatro(x) que representa a func¸a˜o constante igual a 4.
zero(x) = λx.0 : N→ N (constante zero)
suc(x) = λx.x + 1 : N→ N (sucessor)
quatro(x) = (constante quatro)
Exerc´ıcio 65. Dada a func¸a˜o recursiva abaixo, calcule ad(1, 3).
ad(x, 0) = id(x)
ad(x, y + 1) = proj33(x, y + 1, suc(ad(x, y)))
Exerc´ıcio 66. Calcule, passo a passo, as seguintes func¸o˜es recursivas parciais:
a) suc(14) = b) id(32) = c) proj42(12, 3, 50, 46) = d) zero(9) =
e) ad(8, 3) = f) ant(19) = g) sub(10, 2) = h) mul(2, 4) =
i) exp(2, 3)
16
Para consulta:
Func¸o˜es ba´sicas:
constzero := {} → N constzero = 0 (func¸a˜o constante zero)
suc(x) : N→ N suc(x) = x+ 1 (func¸a˜o sucessor)
projni(x1, ..., xn) : Nn → N projn1(x1, ..., xn) = xi (func¸a˜o projec¸a˜o)
Func¸a˜o Identidade:
id(x) = proj11(x)
Func¸a˜o Zero:
zero(0) = constzero
zero(y + 1) = proj22(y, zero(y))
Func¸a˜o Adic¸a˜o:
ad(x, 0) = id(x)
ad(x, y + 1) = proj33(x, y, suc(ad(x, y)))
Func¸a˜o Antecessor:
ant(0) = constzero
ant(y + 1) = proj21(y, ant(y))
Func¸a˜o Subtrac¸a˜o:
sub(x, 0) = id(x)
sub(x, y + 1) = proj33(x, y, ant(sub(x, y)))
Func¸a˜o Multiplicac¸a˜o:
mul(x, 0) = zero(x)
mul(x, y + 1) = ad(proj31(x, y,mul(x, y)), proj33(x, y,mul(x, y)))
Func¸a˜o Exponenciac¸a˜o:
exp(x, 0) = suc(zero(x))
17
exp(x, y + 1) = mul(proj31(x, y, exp(x, y)), proj33(x, y, exp(x, y)))
Func¸o˜es Recursivas
Exerc´ıcio 67. Defina os conceitos abaixo:
• Problema soluciona´vel
• Problema na˜o-soluciona´vel;
• problema parcialmente soluciona´vel;
• Problema computa´vel;
• Problema de decisa˜o;
• Problema polinomial (trata´vel);
• Classe P de problemas;
• Algoritmo verificador;
• Classe NP de problemas;
• problema NP-completo;
18