·

Ciência da Computação ·

Algoritmos em Grafos

Send your question to AI and receive an answer instantly

Ask Question

Preview text

UERJ Instituto de Matematica e Estatıstica Departamento de Informatica e Ciˆencia da Computacao IMEUERJ Professor Luerbio Faria Segunda prova de Teoria da Computacao Data 24052021 1 60 Para cada uma das linguagens L1 L2 1 L1 w a3ib2jcjd2i w 2 a b c d i j 2 N 2 L2 w akb w 2 a b k k 2 N a 10 Mostre que a linguagem e nao regular b 10 Apresente um autˆomato de pilha que reconheca a linguagem por pilha vazia e estado final c 10 Apresente uma gramatica livre de contexto que gere a linguagem 2 25 Maquina de Turing Considere L abncn n 2 N abc ababcc abababccc ababababcccc a 20 Projete uma maquina de Turing M K Γ δ q0 F que reconheca L b 05 Enumere as transicoes da maquina que vocˆe fez e mostre que ab2c2 2 LM 3 20 Verdadeiro ou Falso a Toda gramatica regular e livre de contexto Com Justificativa se Verdadeira e Contraexemplo se Falsa b A Tese de Church diz que a Maquina de Turing e a formalizacao do conceito de procedimento com putacional Com Verdadeiro ou Falso com correcao c O Teorema de Godel diz que Consistˆencia implica em Completude Com Verdadeiro ou Falso com correcao d Nao existe uma maquina de Turing a qual dada uma maquina de Turing M e uma entrada x 2 seja capaz de decidir se M para com x Com Verdadeiro ou Falso com correcao