P1 - 2017/2 - Turma B - Teoria da Computação - UFRGS

Prévia do material em texto

Teoria da Computação – INF05501 – Prova 1 – Turma B
02 de Outubro de 2017
Nome: RESOLUÇÃO Cartão UFRGS:
Considere a seguinte descrição de máquina, denominada PSX. A memória de trabalho
consiste de uma string formada pelos símbolos ×, �, 4, e © . A entrada é uma string, e a saída
é uma string (formada pelos mesmos símbolos). A função de entrada e a função de saída são
ambas a função identidade sobre strings. Dada uma string não vazia, denominaremos cursor
o primeiro símbolo da mesma.
A máquina PSX possui os seguintes testes, com respectivas interpretações descritas a seguir:
1. triangle? — testa se a string não é vazia e o cursor é 4
2. cross? — testa se a string não é vazia e o cursor é ×
3. square? — testa se a string não é vazia e o cursor é �
4. circle? — testa se a string não é vazia e o cursor é ©
5. empty? — testa se a string é vazia
A máquina PSX possui as seguintes operações, com respectivas interpretações descritas a seguir:
1. addTriangle — prefixa 4 na string da memória
2. addSquare — prefixa � na string da memória
3. addCross — prefixa × na string da memória
4. addCircle — prefixa © na string da memória
5. delete — se string vazia, não faz nada. Caso contrário, deleta o cursor da string da
memória.
6. reverse — inverte a string da memória.
Considere o seguinte programa para PSX:
P1 =
1
1. (a) [11/2pt]Apresente a computação do programa P1 na máquina PSX sobre as seguintes strings
de entrada:
1. © ×× 4 © �.
2. � ×× ×.
Você pode colocar rótulos diretamente sobre o diagrama (para evitar reescrever o
programa em instruções rotuladas).
Conversão do diagrama de P1 para instruções rotuladas:
1: if square? then goto 2 else goto 3
2: do addCross goto 0
3: if empty? then goto 4 else goto 5
4: do addCircle goto 0
5: do delete goto 6
6: if triangle? then goto 0 else goto 3
Computação de P1 para entrada © ×× 4 © �:
Rótulo Memória
1 © ×× 4 © �
3 © ×× 4 © �
5 © ×× 4 © �
6 × × 4 © �
3 × × 4 © �
5 × × 4 © �
6 × 4 © �
3 × 4 © �
5 × 4 © �
6 4 © �
0 4 © �
Computação de P1 para entrada � ×× ×:
Rótulo Memória
1 � ×× ×
2 � ×× ×
0 × � ×× ×
(b) [11/2pt]O programa iterativo descrito abaixo é PSX-equivalente a P1? Justifique sua resposta.
se square? então addCross
senão (até empty?
faça (delete; (se triangle? então X
senão addCircle)))
Seja P2 o programa iterativo acima. P1 e P2 não são PSX-equivalentes pois as suas
funcões computadas não são iguais na máquina PSX. Em particular,
〈P1,PSX〉(© 44) = 4 4 e 〈P2,PSX〉(© 44) = ⊥
2. [1pt]Considere o seguinte programa recursivo Q para a máquina Norma.
Q é R1 onde
R1 def X:=X+1; R2
R2 def se X=0 então X senão R3
R3 def X:=X-1; Y:=Y+1; Y:=Y+1; se X=0 então X senão R3
2
Determine a função computada 〈Q,Norma〉.
〈Q,Norma〉(n) = 2n+ 2
3. [1pt]O conjunto T = { f | f : N → {a, b, c}} (conjunto de todas as funções com domínio N e
contradomínio {a, b, c}) é contável ou não-contável? Justifique.
O conjunto T inclui todas as funções do tipo N→ {a, b}. Interpretando a como “pertence
ao subconjunto” e b como “não pertence ao subconjunto”, temos em T todas as funções ca-
racterísticas dos subconjuntos de números naturais. É sabido que a coleção de subconjuntos
dos naturais P(N) é incontável, portanto T também é incontável.
4. [1pt]Considere as seguintes afirmações:
I Podemos sempre encontrar um programa recursivo R fortemente equivalente a um
programa iterativo I fornecido. Verdadeiro.
II O algoritmo de verificação de equivalência forte de programas monolíticos responde à
seguinte pergunta: dois fluxogramas F1 e F2 são equivalentes em todas as possíveis
máquinas? Verdadeiro.
III A máquina Norma1 (Norma contendo somente o registrador X, com saída em X) simula
a máquina Norma.
Falso. Dois registradores no mínimo são necessários.
Estão corretas somente as afirmações
A. I e II
B. I, II e III
C. II e III
D. I e III
E. todas as afirmações estão erradas
5. [2pt]Apresente uma subrotina para a máquina Norma que realize o teste
A < B?
isto é, determine se o conteúdo do registrador A é estritamente menor que o conteúdo do
registrador B. A rotina deve preservar os valores dos registradores A e B, e os registradores
auxiliares que forem utilizados devem conter o valor 0 ao final da execução. Todas as
subrotinas utilizadas devem ser declaradas, com exceção de A := 0, A := B (destrutivo),
A := B usando C (não-destrutivo), A := A + B (destrutivo) e A := A + B usando C
(não-destrutivo) que podem ser usadas diretamente sem apresentar a respectiva definição.
3
6. [2pt]A máquina PSX simula a máquina Norma? Justifique descrevendo a simulação (caso res-
posta positiva) ou apresentando um contraexemplo (caso resposta negativa).
PSX simula Norma2:
Entrada: um número de entrada n em Norma2 pode ser representado pela string
n︷ ︸︸ ︷× × · · · ש
em PSX, isto é, n símbolos × seguidos de um marcador © .
Saída: uma string de saída s em PSX pode ser convertida em número contando o número
de símbolos × que ocorrem à direita do último marcador © em s. Exemplo: × × © × × ×
é convertida em 3.
Memória: os dois registradores X e Y de Norma2 podem ser representados por uma única
string formada pelos símbolos × e © , contendo exatamente um símbolo © . O número
de ocorrências do símbolo × à esquerda de © representa o registrador X e o número de
ocorrências de × à direita de © representa o registrador Y .
Fluxograma: um fluxograma em Norma2 é traduzido para um fluxograma em PSX. A
tradução das intruções básicas se dá como segue :
• X := X + 1: adicione o símbolo × na frente da string.
• Y := Y + 1: reverta s, adicione ×, reverta s novamente.
• X = 0?: teste se o cursor é © , retornando a resposta.
• Y = 0?: reverta s. Teste se o cursor é © . Se sim, reverta s e retorne verdadeiro. Se
não, reverta s e retorne falso.
• X := X − 1: teste se o cursor é ×. Se sim, delete, não fazendo nada caso contrário.
• Y := Y − 1: reverta s. Teste se o cursor é ×, deletando caso seja e não fazendo nada
caso contrário. Reverta s novamente.
Como a máquina Norma2 simula a máquina Norma, por transitividade da simulação pode-
mos provar que PSX simula Norma.
4