BCC244-Teoria da Computação
Prof. Lucília Figueiredo
DECOM
ICEB - UFOP
Lista de Exercícios 03
Máquinas de Turing - Computabilidade
1. Seja L uma linguagem não livre de contexto. Mostre que:
(a) Se X uma linguagem finita, então L − X não é livre de contexto.
Seja X finita e suponha, por contradição, que L − X seja livre de contexto. Como X
é finita, temos que L ∩ X é finita e, portanto, é livre de contexto, Como a classe das
linguagens livres de contexto é fechada em relação à interseção, teríamos que (L − X) ∪
(L ∩ X) é livre de contexto. Mas (L − X) ∪ (L ∩ X) = L e L não é livre de contexto.
Portanto, se X é finita, então L − X não é livre de contexto.
(b) Se X é uma linguagem regular, então L − X pode ser livre de contexto ou pode não ser.
Considere L − Σ∗ = ∅. Temos que Σ∗ é regular e ∅ é livre de contexto. Por outro lado,
considere L − ∅ = L. Temos que ∅ é regular e L não é livre de contexto. Portanto, se L
não é livre de contexto e X é regular, L − X pode ser livre de contexto ou não.
2. Construa uma MT que reconheça a linguagem a∗ b∗ .
b → b, D
a → a, D
t → t, D
b → b, D
3. Descreva, em linguagem de alto nível, uma MT que reconheça a linguagem {an bn cn | n ≥ 0}.
while current-symbol == a
escreve x, anda para a direita
while current-symbol <> b
escreve o mesmo simbolo lido, anda para direita
escreve y, anda para a direita
while current-symbol <> c
escreve o mesmo simbolo lido, anda para direita
escreve z, anda para a esquerda
while current-symbol <> x
escreve o mesmo simbolo lido, anda para esquerda
escreve x, anda para a direita
if current-symbol == t then aceita else rejeita.
OBS: Note que, se o número de a’s for maior do que o número de b’s ou do que o número de
c’s, a máquina entra em loop e, portanto, o string não será aceito. Se o número de b’s ou de c’s
for maior do que o número de a’s, o símbolo encontrado no final do loop mais externo não será
branco e, portanto, o string não será aceito.
4. Prove que a classe das linguagens Turing-decidíveis (ou recursivas) é fechada em relação as
operações de união, interseção e concatenação.
5. Prove que a classe das linguagens Turing-reconhecíveis (ou recursivamente enumeráveis) é
fechada em relação as operações de união, interseção e concatenação.
6. Seja L uma linguagem não recursiva.
(a) Mostre que, se X é finita então L − X é não recursiva.
(b) Mostre que L é não recursiva.
(c) Mostre que, se L é LRE, então L não é LRE.
7. POSCOMP 2008 - Assinale a afirmativa INCORRETA:
Existe uma Máquina de Turing U que simula qualquer outra Máquina de Turing M sobre
qualquer entrada w.
A Tese de Church-Turing afirma que o conceito informal de procedimento efetivo é capturado pelo conceito formal de Máquina de Turing.
Uma linguagem é recursivamente enumerável se, e somente se, ela é aceita por alguma
Máquina de Turing.
Existe uma Máquina deTuring T que, dada uma Máquina de Turing M e uma entrada w
para M , T determina, em um número finito de passos, se M pára ou não para a entrada w.
Toda linguagem recursiva é recursivamente enumerável, mas o inverso nem sempre é
verdadeiro.
8. Sejam L e L uma linguagem e o seu complemento, respectivamente. Marque as situações
abaixo que não podem ocorrer:
L e L são ambas recursivas.
L é recursivamente enumerável, mas não é recursiva, e L não é recursivamente enumerável.
L e L são ambas recursivamente enumeráveis, mas não são recursivas.
L é regular e L não é regular.
L é livre de contexto e L não é livre de contexto.
9. Assinale as afirmativas CORRETAS:
Toda Linguagem enumerável é recursivamente enumerável.
Toda Linguagem Livre de Contexto é decidível.
Existem linguagens Regulares que não são decidíveis.
Toda linguagem é reconhecível ou é co-reconhecível.
O conjunto de todos os strings sobre um alfabeto Σ é recursivamente enumerável.
O conjunto de todas as MTs é enumerável, mas não é recursivamente enumerável.
O conjunto de todos as MTs cuja linguagem é vazia é enumerável mas não é recursivamente enumerável.
10. Com relação a linguagens e seus aceitadores (ou reconhecedores), marque as afirmativas a
seguir que são corretas.
{w wR | w ∈ {a, b}∗ } é aceita por autômato de pilha determinista.
{w c wR | w ∈ {a, b}∗ } é aceita por autômato finito não determinista.
{a2n bm | n, m ≥ 0} é aceita por autômato finito não determinista.
{w c w | w ∈ {a, b}∗ } é aceita por autômato de pilha determinista.
{M | M é uma MT e M pára para alguma entrada } é reconhecida por uma Máquina de
Turing não determinista.
{w w | w ∈ {a, b}∗ } é aceita por uma máquina de Turing que sempre pára.
11. Considere as seguintes linguagens, sobre um dado alfabeto Σ:
ARE = {hD, si | o AFD D aceita a string s}
ERE = {hDi | a linguagem reconhecida pelo AFD D é ∅}
AT M = {hM, si | a máquina de Turing M aceita a string s}
ET M = {hM i | a linguagem reconhecida pela máquina de Turing M é ∅}
ALLT M == {hM i | a linguagem reconhecida pela máquina de Turing M é Σ∗ }
Marque a afirmativas CORRETA:
Todas as linguagens acima são enumeráveis.
Todas as linguagens acima são decidíveis.
Apenas as linguagens ET M e ALLT M não são reconhecíveis.
A linguagem ET M é co-reconhecível.
A linguagem ALLT M não é reconhecível, nem co-reconhecível.
A linguagem AT M é reconhecível e co-reconhecível.
12. Um problema de decisão é um problema cuja resposta é sim ou não. Por exemplo, determinar se
um string w pertence a uma linguagem L, ou determinar uma máquina de Turing M reconhece
a linguagem vazia, ou determinar se x + y = z. Uma instância de um problema de decisão é um
caso particular deste problema. Por exemplo, 3 + 2 = 5 é uma instância positiva do problema
x + y = z e 2 + 3 = 10 é uma instâncoa negativa deste problema. Dizemos que um problema
de decisão P é decidível, se existe uma máquina de Turing que decide este problema, isto é,
que é capaz de determinar, dada uma instância qualquer do problema como entrada, se esta é
uma instância positiva ou não é.
Dizemos que um problema de decisão P reduz para outro problema de decisão P 0 , se existe um
algoritmo (ou máquina de Turing) que converte cada instância do Problema P em uma instância
do problema P 0 .
Considere três problemas de decisão P1 , P2 e P3 . Sabemos que P1 é decidível e P2 não não é
decidível. Marque a afirmativa CORRETA:
P3 é decidível se P1 reduz para P3 .
P3 não é decidível se P3 reduz para P2 .
P3 não é decidível se P2 reduz para P3 .
P3 é decidível se P3 reduz para o complemento de P2 .
13. (1,0 ponto) O "poder computacional" de um computador consiste na classe de problemas que
podem ser resolvidos por meio de programas executados nesse computador. Considere um
computador moderno usual, tal como o seu PC. Com base nos resultados da teoria de máquinas
de Turing, analise as seguintes afirmativas e marque aquelas que são CORRETAS:
Um computador com vários processadores, que pode executar computações em paralelo,
tem o mesmo poder computacional que outro que tenha um único processador.
Um computador que tenha uma memória com acesso apenas sequencial tem menor poder
computacional do que outro que tenha acesso direto a qualquer posição de memória.
Um computador com vários dispositivos de memória tem maior poder computacional que
outro computador com apenas uma área de memória, com a mesma capacidade total de
todos os dispositivos de armazenamento do primeiro.
Se o computador tem vários dispositivos de memória e pode ler dados simultaneamente
em cada um desses dispositivos, ele tem maior poder computacional do que se apenas
pudesse ler dados de um único dispositivo de cada vez.
Um computador que tenha apenas um tipo de instrução, que pode ler o valor em uma posição qualquer de memória e determinar o valor a ser escrito na memória e a próxima instrução a ser executada tem o mesmo poder computacional que um computador moderno, que
inclui instruções para carregar e armazenar dados, com diversos tipos de endereçamento à
memória, intruções de teste e desvio, intruções para realizar operações aritméticas etc.
14. A tabela a seguir resume informações que aprendemos ao longo do curso sobre a hierarquia
de linguagens formais – Hierarquia de Chomsky. Preencha as lacunas da tabela, usando como
modelo as informações já preenchidas.
Obesrvações:
(a) Utilize a seguinte simbologia: AF (Autômato de Estados Finitos), AP (Autômato de Pilha), MT (Máquina de Turing), ER (Expressão Regular), GLC (Gramática Livre de Contexto), GSC (Gramática Sensível ao Contexto), GI (Gramática Irrestrita).
(b) Na coluna entitulada "Exemplo", dê uma exemplo de uma linguagem que pertença à classe
indicada e que não pertença à classe imediatamente anterior.
(c) Na coluna entitulada "ND", responda à pergunta "Não determinismo introduz maior poder
computacional ao modelo?".
(d) Na coluna entitulada "Fecho", indique em relação a quais das seguintes operações a classe
de linguagens é fechada: ∪ (união), • (concatenação), ? (fecho de Kleene), ∩ (interseção)
e (complemento).
Classe
Regular
Livre
de
Contexto
Sensível ao
Contexto
Recursiva
Recursiv.
enumerável
Hierarquia de Linguagens
Especificação Exemplo
Reconhecedor
?
(0|1)
{0p | p é primo} MT limitada
linearmente
Gramática
irrestrita
Gramática
irrestrita
ND
Fecho
?
∪, •, ?, ∩,
não
∪, •, ?, ∩,