Lista de Exercicios - Linguagens Formais e Autômatos - Máquinas de Turing e Gramáticas

1 60 Para cada uma das linguagens L₁ L₂ 1 L₁ w a³ib²jcj d2i w a b c d i j N 2 L₂ w aⁱbℓ w a b k ℓ k ℓ N a 10 Mostre que a linguagem é não regular b 10 Apresente um autômato de pilha que reconheça a linguagem por pilha vazia e estado final c 10 Apresente uma gramática livre de contexto que gere a linguagem 2 25 Máquina de Turing Considere L abⁿcⁿ n N abc ababcc abababccc ababababcccc a 20 Projete uma máquina de Turing M K Σ Γ δ q0 F que reconheça L b 05 Enumere as transições da máquina que você fez e mostre que ω ab²c² LM 3 20 Verdadeiro ou Falso a Toda gramática regular é livre de contexto Com Justificativa se Verdadeira e Contraexemplo se Falsa b A Tese de Church diz que a Máquina de Turing é a formalização do conceito de procedimento computacional Com Verdadeiro ou Falso com correção c O Teorema de Gödel diz que Consistência implica em Completude Com Verdadeiro ou Falso com correção d Não existe uma máquina de Turing a qual dada uma máquina de Turing M e uma entrada x Σ seja capaz de decidir se M pára com x Com Verdadeiro ou Falso com correção