ACFrOgBiwQKdpg_dKDnyaUfz2hXW60N_7_HgjH5C7xG67djhUPSHrwcICiJfmgOk4D38AB0P2VCCoCVJvX-lYXgoZB7zenT_Rxi2Avd7hydUVVnIwiqrdlCzXwtE8ONkSFam9NF7C6kiD9un_H90

Prévia do material em texto

Avaliação de 2ª Unidade (PLE 2020.4)
Curso: Ciência da Computação Disciplina: Teoria da Computação
Profa: Maria Sibaldo
Aluno: Data: 18/02/2021
Orientações para a avaliação:
Obs.: LEMBREM-SE QUE A PROVA É SEM CONSULTA, E CASO ALGUÉM DESRESPEITE ALGUMA
RESTRIÇÃO TERÁ A NOTA AUTOMATICAMENTE COMO ZERO (0). 
1) (2,5 pontos) Considere a seguinte gramática: 
G = ({S, X, Y, A}, {a, b}, P, S), onde:
P = {S -> XY, 
X -> AXA | , Y -> YA | ,
A -> a | b} 
Coloque esta gramática na Forma Normal de Greibach, 
apresentando cada etapa deste processo.
2) (2,0 pontos) Desenvolva um autômato com pilha que aceite a
seguinte linguagem:
a) {0n1k | n k 2n},   alfabeto {a, b}
3) (2,5 pontos) Apresente uma Máquina de Turing M que multiplica
um número por 2. Alfabeto = {1}, o valor das entradas e saídas
está representada pela quantidade de 1's. 
Exemplos: Entrada (11), saída (1111); entrada (111), saída
(111111).
4) (1,0 ponto) O que diz a tese de Church-Turing?
5) (2,0 pontos)Se fosse descoberto um algoritmo polinomial para
um problema considerado indecidível, que consequência haveria
e por quê?