Universidade Federal de Uberlândia
Mestrado em Ciência da Computação
Solução da 1a Prova de Teoria da Computação - 05/04/2011
Questão 1 (Valor = 12 pontos)
Sejam IN FDF A = {< M >| M é um autômato tal que L(M) é infinita.},
IN FGLC = {< M >| M é uma gramática livre do contexto tal que L(M) é infinita.},
IN FT M = {< M >| M é uma máquina de Turing tal que L(M) é infinita.}. Pede-se:
1. (Valor = 4 pontos) IN FDF A é decidı́vel ? Justifique sua resposta.
Solução: Sim, IN FDF A é decidı́vel. A seguinte máquina de Turing decide IN FDF A :
M = No input < A > faça:
• Testa se < A > é um string correspondente à codificação de um autômato finito
determinista. Se for, vai para o próximo passo, caso contrário rejeita.
• Seja n = número de estados de A.
• Constrói todas os strings w com comprimento entre n e 2n, isto é, n ≤| w |< 2n.
Sejam w1 , ..., wk estes strings.
• Executa o autômato A sobre cada um destes strings wi .
• Se nenhum for aceito, rejeita.
• Se algum for aceito, aceita.
Este algoritmo é baseado no seguinte resultado sobre autômatos finitos: A linguagem L(A)
reconhecida por um autômato A é infinita se e somente se existe uma palavra w ∈ L(A)
tal que n ≤| w |< 2n, onde n = número de estados de A.
Demonstração:
• Se existir uma palavra w ∈ L(A) com comprimento ≥ n, sabemos, pelo Lema do
bombeamento para linguagens regulares que L(A) é infinita (já que w = vxy e vxi y ∈
L(A) para todo i ≥ 0.
• Reciprocamente, suponhamos que L(A) seja infinita. Então, é claro que deve existir
uma palavra w ∈ L(A) com | w |≥ n. Se | w |< 2n, temos nosso resultado. Suponhamos então que toda palavra de L(A) tenha comprimento ≥ 2n ou < n. Como
L(A) é infinita, existe palavra w de L(A) com comprimento ≥ 2n. Pelo lema do
bombeamento para linguagens regulares, sabemos que w = vxy, com 0 <| x | ≤ n
e vx0 y ∈ L(A). Logo: n ≤| vy |<| w | e vy ∈ L(A). Se | vy |< 2n, chegamos ao
nosso resultado. Caso contrário repetimos o raciocinio para vy e encontramos uma
outra palavra w1 em L(A) com comprimento > n e menor do que | vy |. Repetindo
este processo um número finito de vezes encontraremos uma palavra de L(A) com
comprimento entre n e 2n.
2. (Valor = 4 pontos) IN FGLC é decidı́vel ? Justifique sua resposta.
Solução: Sim, IN FGLC é decidı́vel. A demonstração é análoga à da questão anterior,
utilizando o lema do bombeamento para gramáticas livres do contexto, como segue: Consideramos a máquina de Turing S que decide a linguagem : L = {< G, w >| w ∈ L(G)}.
Já vimos em aula que esta máquina existe. Considere a seguinte máquina de Turing que
decide IN FGLC :
M = No input < G > faça:
• Testa se < G > é um string correspondente à codificação de uma gramática livre do
contexto. Se for, vai para o próximo passo, caso contrário rejeita.
• Seja n = 2k−1 , onde k = número de variáveis de G.
• Constrói todos os strings w com comprimento entre n e 2n, isto é, n ≤| w |< 2n.
Sejam w1 , ..., wm estes strings.
• Executa a máquina S sobre cada um destes strings wi .
• Se nenhum for aceito, rejeita.
• Se algum for aceito, aceita.
Este algoritmo é baseado no seguinte resultado sobre gramáticas livres do contexto: A
linguagem L(G) gerada por uma gramática livre do contexto G é infinita se e somente se
existe uma palavra w ∈ L(G) tal que n ≤| w |< 2n, onde n = 2k−1 e k = número de
variáveis de G.
Demonstração:
• Se existir uma palavra z ∈ L(A) com comprimento > n, sabemos, pelo Lema do
bombeamento para linguagens regulares que L(G) é infinita (já que z = uvwxy e
uv i wxi y ∈ L(G) para todo i ≥ 0).
• Reciprocamente, suponhamos que L(G) seja infinita. Então, é claro que deve existir
uma palavra z ∈ L(G) com | z |> n. Se | z |< 2n, temos nosso resultado. Suponhamos
então que toda palavra de L(A) tenha comprimento ≥ 2n ou ≤ n. Como L(G) é
infinita, existe palavra z ∈ L(G) com comprimento ≥ 2n. Pelo lema do bombeamento
para linguagens livres do contexto, sabemos que z = uvwxy, com 0 <| vwx | ≤ n.
Portanto | vx | < n já que w ̸= ϵ. Além disto, para todo i ≥ 0 temos que uv i wxi y ∈
L(G). Em particular para i = 0 temos que uv 0 wx0 y = uwy ∈ L(G). | uwy | =
| z | − | vx | > 2n−n = n. Logo: n <| uwy | e uwy ∈ L(G). Se | uwy |< 2n, chegamos
ao nosso resultado. Caso contrário repetimos o raciocinio para a palavra uwy ∈ L(G)
e encontramos uma outra palavra w1 em L(G) com comprimento > n e menor do
que | uwy |. Repetindo este processo um número finito de vezes encontraremos uma
palavra de L(G) com comprimento entre n e 2n.
3. (Valor = 4 pontos) IN FT M é decidivel ? Justifique sua resposta.
Solução: Não, IN FT M é indecidı́vel. Para provar isto, vamos apresentar uma reduçäo
f : AT M → IN FT M , tal que f (< M, w >) = M ′ , onde M ′ é a máquina de Turing definida
como se segue:
M ′ = No input x faça:
1. Executa M em w;
2. Se M aceita w, M ′ entra em qa ;
3. Se M rejeita w, M ′ entra em qr ;
É fácil ver que L(M ′ ) = Σ∗ (conjunto de todos os strings sobre o alfabeto Σ) se M aceita
w. E L(M ′ ) = ∅ se M não aceita w. Logo L(M ′ ) é infinita se e somente se M aceita w.
Logo, provamos que AT M se reduz a IN FT M . Como AT M é indecidı́vel, então IN FT M é
indecidı́vel.
Questão 2 (Valor = 10 pontos)
Considere a seguinte linguagem: A ={< M > | M é uma máquina de Turing e L(M ) ̸= ∅}.
1. (Valor = 5 pontos) Mostre que A é Turing-reconhecı́vel.
Solução:
Temos de exibir uma máquina de Turing S que reconhece a linguagem A, isto é, S(< M >)
= “sim” se e somente se < M >∈ A, isto é, se e somente se M é uma máquina de Turing
que aceita algum string. A seguinte máquina S faz este trabalho:
S = No input < M > faça:
1. Seja {x1 , x2 , x3 , ...} o conjunto de todos os strings sobre o alfabeto de M . Execute o
seguinte até que M atinja o estado qa :
2.1 passo 1 de M em x1 ,
2.2 passo 2 de M em x1 , passo 1 de M em x2 ,
2.3 passo 3 de M em x1 , passo 2 de M em x2 ,passo 1 de M em x3 ,
2.4 ...
3. Entra no estado qa .
É claro que S < M > = qa se e somente se L(M ) ̸= ∅. Logo S é uma máquina de Turing
que reconhece a linguagem A. Portanto A é Turing-reconhecı́vel.
2. (Valor = 5 pontos) O que você acha a respeito da decidibilidade de A ? Justifique sua
resposta.
Solução: A não é decidı́vel. De fato, vamos mostrar que AT M se reduz a A. Considere a
transformação f : AT M → A, tal que f (< M, w >) = M ′ , onde M ′ é a máquina de Turing
definida como se segue:
M ′ = No input x faça:
1. Se x ̸= w, entra em qr ;
2. Se x = w, executa M em w;
3. Se M aceita w, M ′ entra em qa ;
4. Se M rejeita w, M ′ entra em qr ;
É fácil ver que L(M ′ ) = {w} se M aceita w e L(M ′ ) = ∅ se M não aceita w. Logo < M ′ >
∈ A se e somente se < M, w > ∈ AT M .
Questão 3 (Valor = 10 pontos)
Seja L = {< M >| M é máquina de Turing tal que M pára em algum input }. O objetivo desta
questão é mostrar que L é indecidı́vel.
• (Valor = 3 pontos) É possivel utilizar o Teorema de Rice para mostrar que L é indecidivel ? Justifique sua resposta.
Solução: Não é possı́vel, pois a 3a condição da hipótese do Teorema de Rice não é verificada: Existem máquinas de Turing M1 e M2 tais que L(M1 ) = L(M2 ) mas M1 ∈ L e M2
̸∈ L. De fato, considere as máquinas de Turing descritas abaixo:
M1 = No input x faça:
1. Entra em loop.
M1 = No input x faça:
1. Pára em qr .
Temos que L(M1 ) = L(M2 ) = ∅. Mas M2 ∈ L e M1 ̸∈ L.
• (Valor = 3 pontos) Prove que L é indecidı́vel SEM utilizar o Teorema de Rice.
Solução: Considere a transformação f : AT M → L, tal que f (< M, w >) = M ′ , onde M ′
é a máquina de Turing definida como se segue:
M ′ = No input x faça:
1. Se x ̸= w, entra em loop;
2. Se x = w, executa M em w;
3. Se M aceita w, M ′ entra em qa ;
4. Se M rejeita w, M ′ entra em loop;
É fácil ver que se M aceita w então M ′ pára no input w, logo M ′ ∈ L. Se M não aceita
w então M ′ entra em loop para qualquer input x, logo M ′ ∈
̸ L.
• (Valor = 4 pontos) L é Turing reconhecı́vel ? Justifique sua resposta.
Solução: Sim L é Turing reconhecı́vel. Temos de exibir uma máquina de Turing S que
reconhece a linguagem L, isto é, S(< M >) = “sim” se e somente se < M >∈ L, isto
é, se e somente se M é uma máquina de Turing que pára para algum string. A seguinte
máquina S faz este trabalho:
S = No input < M > faça:
1. Seja {x1 , x2 , x3 , ...} o conjunto de todos os strings sobre o alfabeto de M . Execute o
seguinte até que M atinja o estado qa ou qr :
2.1 passo 1 de M em x1 ,
2.2 passo 2 de M em x1 , passo 1 de M em x2 ,
2.3 passo 3 de M em x1 , passo 2 de M em x2 ,passo 1 de M em x3 ,
2.4 ...
3. Entra no estado qa .
É claro que S < M > = qa se e somente se M pára ao ser executada em algum string
xi . Logo S é uma máquina de Turing que reconhece a linguagem L. Portanto L é Turingreconhecı́vel.