Cap 5
Cap 5
Cap 5
Decidibilidade
Como já foi dito nos capı́tulos anteriores, existem vários problemas indecidı́veis, alguns
deles de formulação bastante simples. Neste capı́tulo serão apresentados alguns desses
problemas.
Este capı́tulo será iniciado pela apresentação da denominada tese de Church-Turing,
que afirma que a máquina de Turing é um formalismo que captura a noção de com-
putação efetiva. Em seguida, será visto como as instâncias de um problema de decisão
podem ser codificadas (representadas) de forma que possam ser alimentadas como en-
tradas para uma MT. Em seguida, na Seção 5.3, será mostrado que quaisquer MTs
podem ser codificadas e apresentadas como entrada para uma MT conhecida como
“máquina de Turing universal”, uma MT que simula qualquer MT fornecida como
entrada. O primeiro problema de decisão indecidı́vel será analisado na Seção 5.4: o
problema da parada para MTs. Será também apresentada uma linguagem que não é
LRE, assim como uma liguagem que é LRE mas não é recursiva. Na Seção 5.5 será
apresentada a técnica de redução de problemas, de forma que uma série de problemas
indecidı́veis sejam determinados como tais, por meio dessa técnica, na Seção 5.6.
243
244 Editora Thomson Introdução aos fundamentos da computação
mesmas entradas, execução em tempo finito etc., vários formalismos foram propostos
no intuito de capturar, de forma precisa (formal), o conceito de computação efetiva. A
partir de uma caracterização formal, seria possı́vel, então, mostrar que certos problemas
seriam computáveis, ou seja, existiriam algoritmos para eles, e que outros não seriam
computáveis.
É interessante observar que, já naquela época (final da década de 1930), vários
formalismos foram propostos que vieram a revelar a mesma expressividade, apesar das
suas diferentes “aparências”. Alguns desses formalismos são:
• máquinas de Turing;
• sistemas de Post;
• funções µ-recursivas;
• λ-cálculo.
Os computadores digitais, tanto os mais antigos quanto os mais modernos, foram
construı́dos com um conjunto de instruções que lhes dão um poder computacional
idêntico ao das máquinas de Turing e ao dos outros formalismos anteriormente cita-
dos.1 Mais modernamente, as linguagens de programação de alto nı́vel, como Java,
C, Pascal etc., com o mesmo poder expressivo, apareceram no intuito de facilitar a
tarefa de programação propriamente dita. Mas, não se deve perder de vista que tais
linguagens não apresentam maior expressividade do que, por exemplo, as MTs, embora
sejam, obviamente, muito mais adequadas do ponto de vista prático para a confecção
de algoritmos.
Entre os diversos formalismos matemáticos propostos, a máquina de Turing é um
dos mais aderentes aos computadores atuais, isto é, pode-se considerar que a máquina
de Turing captura a parte “essencial”, aquela responsável, em última análise, pelo
poder computacional dos computadores atuais. Já de um ponto de vista mais geral,
como os formalismos e linguagens já mencionados são equivalentes do ponto de vista
de expressividade, poder-se-ia dizer que a noção de “computação” seria o que existe de
comum entre todos eles, ou, por outro lado, cada um deles apresenta uma abordagem
diferente para o conceito de computabilidade.
A tese de Church-Turing pode ser assim enunciada:
Se uma função é efetivamente computável, então ela é computável por meio
de uma máquina de Turing.
Ou, equivalentemente: todo algoritmo pode ser expresso mediante uma MT.
A noção de computação efetiva não é definida formalmente. Portanto, não há
como provar que a tese de Church-Turing é correta. No entanto, a proliferação de
formalismos nunca mais expressivos que o da máquina de Turing constitui evidência em
seu favor. Dada a equivalência dos vários formalismos e linguagens, a tese de Church-
Turing, mesmo que implicitamente, equipara a classe das funções computáveis à classe
1
Estritamente falando, o poder computacional associado aos formalismos matemáticos citados é maior
que o de qualquer computador real, em virtude do fato de que um computador real tem uma memória
limitada.
Newton José Vieira Capı́tulo 2: Máquinas de estados finitos 245
de funções que podem ser expressas em qualquer um deles. Assim, por exemplo, a tese
implica que “se uma função for efetivamente computável, então ela será computável
por meio de um programa escrito na linguagem C”.
A tese de Church-Turing, quando particularizada para problemas de decisão, po-
deria ser assim enunciada: se um problema de decisão tem solução, então existe uma
MT que o soluciona. Dessa forma, para mostrar que um problema de decisão não tem
solução, basta mostrar que não existe MT que o soluciona. Por outro lado, dada a
equivalência dos diversos formalismos, um problema de decisão não tem solução se não
for possı́vel expressar uma solução em qualquer um dos mesmos. Assim, por exemplo,
se não existir um programa em C que seja uma solução para um problema de decisão,
então esse problema de decisão é insolúvel.
Uma caracterı́stica importante de qualquer um dos formalismos citados é o que
se denomina auto-referência. Por exemplo, é possı́vel ter MTs que manipulam MTs:
para isso, basta codificar (ou representar) a MT a ser manipulada, usando-se um al-
fabeto apropriado, antes de supri-la como entrada. No caso de uma linguagem de
programação, é possı́vel ter programas que manipulam programas: um programa em
Java pode receber como entrada um programa escrito em Java e manipulá-lo como
dado. Na Seção 5.2, vamos ver como isso pode ser feito para MTs.
A caracterı́stica mencionada no parágrafo anterior propicia a possibilidade de se
construir uma máquina universal, ou seja, uma MT (ou programa em uma linguagem
de programação) que seja capaz de simular uma MT (programa) qualquer suprida como
argumento. Na Seção 5.3, será apresentada uma máquina desse tipo: uma máquina de
Turing universal.
A possibilidade de auto-referência é uma caracterı́stica fundamental que levou à
descoberta de funções não computáveis. Um exemplo disso será visto na Seção 5.4:
não existe MT que determine se uma MT arbitrária vai parar ou não ao processar certa
entrada. Ou ainda, não existe programa em C que determine se um programa em C vai
parar ou não ao processr certa entrada. Na verdade, vários outros problemas similares,
que envolvem o processamento de MTs por MTs são insolúveis, como será mostrado
nos capı́tulos subsequentes.
Como já foi dito na Seção 1.4, a solução de um problema de decisão P é um algoritmo
que dá a resposta correta para cada instância p ∈ P . Dada a tese de Church-Turing,
a solução de P pode ser expressa por meio de uma máquina de Turing que, para cada
instância p ∈ P , se a resposta para p for “sim”, para em um estado final, e se a
resposta for “não”, para em um estado não final. Dessa forma, a máquina de Turing
deve reconhecer a linguagem recursiva que consta de todas as instâncias p para as quais
a resposta é “sim”.
246 Editora Thomson Introdução aos fundamentos da computação
Implı́cito no parágrafo anterior está o fato de que uma máquina que solucione um
problema P deve receber como entrada uma palavra que represente uma instância de
P . Assim, o primeiro passo para solucionar um problema de decisão P é projetar uma
representação para as instâncias de P utilizando-se um certo alfabeto Σ. Quando o PD
consta de uma única instância, na verdade ela não precisa ser representada, ou, por
outro lado, qualquer palavra serve para representá-la (λ, por exemplo). E mais, se o PD
consta de um número finito n de instâncias, nenhuma delas precisa ser representada,
ou, de outra forma, quaisquer n palavras servem para representar as n instâncias.
O problema da representação se torna importante quando o PD tem uma infinidade
de instâncias.2
Cada instância p de um PD P pode ser identificada com uma sequência v1 ,
v2 , . . . , vk de valores especı́ficos para os k parâmetros de P (e vice-versa). Assim,
a representação de p pode ser feita codificando-se a sequência v1 , v2 , . . . , vk , o que é
feito associando-se (pelo menos) uma palavra de Σ∗ a tal sequência. Essa associação
deve satisfazer os seguintes requisitos:
1. Para cada instância de P deve existir pelo menos uma palavra de Σ∗ que a
represente.
2. Cada palavra de Σ∗ deve representar no máximo uma instância de P .
3. Para cada palavra w ∈ Σ∗ , deve ser possı́vel determinar se ela representa ou não
alguma instância de P . Ou seja, o problema de determinar se w representa uma
instância deve ser decidı́vel.
sim
Rhv1 , . . . , vn i M
não
A notação Rhv1 , v2 , . . . , vn i será utilizada para designar qualquer palavra w que re-
presente a instância p correspondente à sequência de valores de parâmetros v1 , v2 ,. . . ,vn .
Uma máquina de Turing M que soluciona um PD, que receba como entrada v1 , v2 , . . . , vn ,
será representada esquematicamente como mostrado na Figura 5.1. Nessa figura,
mostra-se que uma entrada para M é qualquer representação Rhv1 , v2 , . . . , vn i para
uma instância do PD, e que a saı́da pode ser sim ou não. Acima das setas indicando
sim e não, para efeitos de clareza, pode-se colocar descrições do que significa a respec-
tiva resposta (veja, por exemplo, a Figura 5.2). Supondo que a representação para o
PD em questão seja feita a partir do alfabeto Σ, então para cada w ∈ Σ∗ , a máquina M
responde sim se (a) w representa alguma instância p (ou seja, se w é Rhv1 , v2 , . . . , vn i
para alguma sequência de parâmetros v1 , v2 ,. . . , vn ) e (b) M para em estado final ao
processar a entrada Rhv1 , v2 , . . . , vn i; e responde não se (a) w não representa qualquer
instância ou (b) se w representa alguma instância mas M para em estado não final ao
processar a mesma. Assim, a entrada para M , na Figura 5.1, pode ser qualquer w ∈ Σ∗ ,
porém a “entrada esperada” é da forma Rhv1 , v2 , . . . , vn i. No entanto, daqui para a
frente, com o objetivo de simplificar a exposição, vamos supor que a entrada esteja
realmente no formato Rhv1 , v2 , . . . , vn i (ou seja, que represente efetivamente alguma
instância).3
3
Tal suposição é coerente com o fato de que o teste para saber se w representa alguma instância pode
(e deve!) ser feito antes da ativação da MT relativa ao PD.
248 Editora Thomson Introdução aos fundamentos da computação
A → aAa | B
B → aB | CC
C → b|λ
Usando os códigos já definidos, sejam Rhr1 i = 11 014 011 014 (código da regra A →
aAa), Rhr2 i = 11 012 (código da regra A → B) etc. Então uma representação para tal
instância, RhH, abai, seria:
13 012 0Rhr1 i00Rhr2 i00Rhr3 i00Rhr4 i00Rhr5 i00Rhr6 i00014 015 014 .
Observe que existem outras representações para essa mesma instância; por exemplo,
mude a ordem de apresentação das regras. Veja também que é possı́vel testar se qual-
quer palavra no alfabeto {0, 1} representa ou não uma instância. Ou seja, a linguagem
w ∈ L(G)
sim
RhG, wi M
w 6∈ L(G)
não
Exercı́cios
1. Seja a seguinte representação de certa gramática G, utilizando-se a codificação
concebida no Exemplo 116:
RhGi = 1101101011101011100101100110111101101111001100.
2. Faça um algoritmo que, dada uma palavra w ∈ {0, 1}∗ , determine se a mesma re-
presenta ou não uma GLC de acordo com a representação criada no Exemplo 116.
Exemplo 117 A seguir, será mostrada uma possı́vel representação de MTs, de forma
que estas possam ser supridas como entrada para outras MTs. O alfabeto usado na
representação será {0, 1}. Seja uma MT qualquer M = (E, Σ, Γ, h, ⊔, δ, i, F ), onde
E = {e1 , e2 , . . . , en } e Γ = {a1 , a2 , . . . , ak }. Suponha que e1 = i, a1 = h,a2 = ⊔ e
lembre-se de que Σ ⊂ Γ. Na Tabela 5.1 encontram-se as representações para os estados
e sı́mbolos do alfabeto de fita. Com referência à direção de movimentação do cabeçote,
D será representada por 1 e E por 11. Supondo que F = {f1 , f2 , . . . , fp } e designando
por Rhxi a representação de x, seja x um estado, um sı́mbolo de Γ ou direção de
movimentação do cabeçote, a representação de M tem os seguintes componentes:
• F é representado por uma lista das representações dos estados finais separados
por 0, ou seja, RhF i = Rhf1 i0Rhf2 i0 · · · Rhfp i;
• cada transição t da forma δ(ei , aj ) = [e′i , a′j , d] é representada pela palavra
Rhti = Rhei i0Rhaj i0Rhe′i i0Rha′j i0Rhdi.
Finalmente, sendo t1 , t2 , . . . , ts as transições de M , uma representação de M é:
RhM i = RhF i00Rht1 i00Rht2 i00 · · · Rhts i.
Exemplo 118 Seja a MT cujo diagrama de estados está ilustrado na Figura 4.4b,
página 210, cuja especificação é aqui reproduzida:
t1 : δ(0, a) = [1, a, D]
t2 : δ(1, b) = [0, b, E].
ou seja,
L(UP ) = {RhM, wi | M para ao processar w}.
Veja que L(UP ) é uma linguagem associada ao PD “dada uma MT M e uma palavra
w, determinar se M para ao processar w”. Na seção a seguir, será mostrado que tal
linguagem não é recursiva. A MT universal pode ser usada como base para a construção
de outras MTs que reconheçam linguagens associadas a PDs que recebam MTs como
entrada. Segue um exemplo.
Exemplo 119 Uma MT que reconhece a linguagem {RhM i | λ ∈ L(M )}, uma lin-
guagem associada ao PD “dada uma MT M , determinar se λ ∈ L(M )”, seria obtida
Newton José Vieira Capı́tulo 2: Máquinas de estados finitos 253
simplesmente alterando o passo 1 da MT universal (ver Figura 5.3) para deixar a fita
2 em branco (ou seja, elimina-se o passo 1, simplesmente).
O exemplo anterior mostra que {RhM i | λ ∈ L(M )} é uma LRE. Na Seção 5.5 será
visto que tal linguagem também não é recursiva e que, portanto, o problema ao qual é
associada não é decidı́vel.
Exercı́cios
1. Faça um algoritmo que determine se uma palavra de {0, 1}∗ é da forma RhM, wi,
supondo a representação do Exemplo 117, página 250.
3. Mostre que a linguagem {RhM, wi | existe estado e tal que M passe duas vezes
por e ao processar w} é recursiva.
M para ao processar w
sim
RhM, wi P
M não para ao processar w
não
M para ao processar w
loop
RhM, wi P′
M não para ao processar w
para
Para isso, basta fazer, para cada par (f, a) tal que δ(f, a) seja indefinido, onde f é
estado final de P e a sı́mbolo de fita de P , δ(f, a) = [l, a, D], onde l é um novo estado.
Nesse último estado, faz-se a máquina entrar em loop assim: δ(l, a) = [l, a, D] para todo
sı́mbolo de fita a de P . Estas seriam as únicas transições a acrescentar a P para se
obter P ′ .
A partir de P ′ , pode-se obter outra máquina, D, conforme ilustra a Figura 5.6.5 A
figura ilustra que D tem transições para (nesta ordem), a partir de uma entrada RhM i:
5
O nome D foi escolhido para lembrar diagonal, visto que a MT D tem uma forte “afinidade” com
o argumento da diagonalização, como será visto após a prova deste teorema.
Newton José Vieira Capı́tulo 2: Máquinas de estados finitos 255
Figura 5.6 A MT D.
1. obter uma representação de RhM i e produzir RhM, RhM ii (via uma sub-MT
RR); e
2. agir como P ′ sobre a palavra produzida anteriormente.
Agora, considere o que acontece se RhDi for submetida como entrada para a MT D: se
D entra em loop ao processar RhDi, é porque D para ao processar RhDi; e se D para
ao processar RhDi, é porque D não para ao processar RhDi. Ou seja,
D para ao processar RhDi
se e somente se
D não para ao processar RhDi.
Contradição! Mas, D pode ser construı́da a partir de P . Assim, P não pode existir e,
portanto, o problema da parada para MTs é indecidı́vel.
Segue uma explicitação do argumento da diagonalização para mostrar que a MT D
do Teorema 40 não pode existir. Ora, D é uma MT que para ao processar RhM i se, e
somente se, M não para ao processar RhM i. Se for considerado que o conjunto das MTs
pode ser enumerado, como de fato é, obtendo-se uma sequência RhM0 i, RhM1 i,RhM2 i,
. . . , isso quer dizer que
D para ao processar RhMi i se, e somente se, Mi não para ao processar RhMi i
para todo i ≥ 0. Veja, então, que D se comporta de forma diferente de Mi ao processar
RhMi i para todo i ≥ 0 (veja a Figura 5.7)!
A prova de que o problema da parada para as linguagens de programação procedu-
rais comuns6 é indecidı́vel segue as mesmas linhas que a prova do Teorema 40, como
pode ser observado a seguir. Será usada uma pseudolinguagem de aparência similar à
que tem sido utilizada até aqui na representação dos algoritmos.
Teorema 41 O problema da parada para as linguagens de programação procedurais
comuns é indecidı́vel.
Prova
Suponha que o procedimento P solucione o PD em questão, de forma que a chamada
P (x, w) retorne verdadeiro se, e somente se, o procedimento de texto x para ao processar
6
Algumas linguagens de programação procedurais “comuns”: Java, C, Pascal.
256 Editora Thomson Introdução aos fundamentos da computação
Note que a prova do Teorema 44 dá um exemplo de linguagem que não é LRE: LP .
Exercı́cios
1. Mostre que o problema da parada para MTs com alfabeto de entrada unitário
é indecidı́vel.
4. Prove que {RhM i | M para em menos de 1000 passos ao processar alguma palavra}
é recursiva, ou seja, que o problema de determinar se uma MT para em menos
de 1000 passos ao processar alguma palavra é decidı́vel.
5. Seja a linguagem {RhM, wi | M não para ao processar w}. Prove que essa lin-
guagem não é recursivamente enumerável. Observe que essa linguagem é LP ,
excluı́das as palavras que não estejam na forma RhM, wi.
6. Mostre que se o problema da parada fosse decidı́vel, então toda LRE seria recursiva.
258 Editora Thomson Introdução aos fundamentos da computação
MT para P
sim
x R y MT para Q
não
RhM, wi R RhM ′ i
RhM, wi R RhG, wi
algoritmo de redução é dado pela técnica referida do Teorema 35, devendo-se considerar
todos os estados de M como estados finais (ou reconhecimento por parada), de forma
que M aceita w se e somente se M para ao processar w. Com isso, a gramática G é tal
que:
Veja que tal PD é decidı́vel se, e somente se, {RhM i | L(M ) satisfaz P } (a linguagem as-
sociada) é recursiva. No caso do problema da fita em branco, por exemplo, o enunciado
é (considera-se reconhecimento por parada):
Esse problema é decidı́vel se, e somente se, a linguagem associada {RhM i | λ ∈ L(M )}
é recursiva. Logo, pelo Teorema 45, essa linguagem não é recursiva.
Para que todos os PDs da classe referida sejam indecidı́veis, basta expurgar dois
tipos de PDs que são, trivialmente, decidı́veis: aqueles em que a propriedade P é sempre
verdadeira e aqueles em que P é sempre falsa, ou seja, aqueles em que a linguagem
{RhM i | L(M ) satisfaz P } é constituı́da de todas as representações de MTs, e aqueles
em que {RhM i | L(M ) satisfaz P } é ∅. Daı́, a definição a seguir.
Newton José Vieira Capı́tulo 2: Máquinas de estados finitos 261
Definição 64 Uma propriedade P de LREs é trivial se for satisfeita por toda LRE ou
por nenhuma.
Exemplos de PDs que envolvem linguagens com propriedades triviais e que, por-
tanto, são (trivialmente) decidı́veis:
Antes de apresentar o Teorema de Rice, que mostra que tais problemas são in-
decidı́veis, assim como qualquer outro no formato geral apresentado anteriormente,
será mostrado à parte que o primeiro problema citado é indecidı́vel, utilizando-se uma
técnica que modifica um pouquinho aquela usada no problema da fita em branco.
Teorema 47 Não existe algoritmo para se determinar se a linguagem aceita por uma
MT arbitrária M não é ∅.
Prova
O problema da parada será reduzido a este de forma similar ao que foi feito para o
problema da fita em branco no Teorema 45. A MT redutora produz RhM ′ i, a partir
de RhM, wi, de forma que:
1. M ′ apaga a entrada;
2. M ′ escreve w;
3. M ′ volta o cabeçote para o inı́cio da fita;
4. M ′ se comporta como M (isto é, o resto da função de transição de M ′ é idêntico
à função de transição de M ).
262 Editora Thomson Introdução aos fundamentos da computação
Observe que a única diferença, com relação a M ′ produzida pela redução no Teorema 45,
é que aqui há um passo anterior: M ′ apaga a entrada que está na fita. Com isso, M ′
ignora qualquer entrada que seja submetida, e se comporta sempre como M com a
entrada w. Assim, tem-se que:
M para ao processar w se e somente se M ′ para ao processar alguma palavra.
É interessante notar que a mesma redução serve para provar o segundo PD citado
anteriormente, já que M ′ parando com alguma entrada, para com todas, e vice-versa:
M ′ para ao processar alguma palavra se, e somente se, M ′ para ao processar qual-
quer entrada.
Segue o Teorema de Rice.
Teorema 48 ( Teorema de Rice) Se P for uma propriedade não trivial de LREs, então
{RhM i | L(M ) satisfaz P } não será recursiva.
Prova
Seja P uma propriedade não trivial.
Caso 1 ∅ não satisfaz P . Seja uma MT MX tal que L(MX ) satisfaz P . Tal MT MX
existe, pois P é não trivial. Observe também que L(MX ) 6= ∅, pois ∅ não satisfaz P .
O problema da parada pode ser reduzido ao de se determinar se L(M ′ ) satisfaz P ,
por meio de uma MT que produz RhM ′ i a partir de RhM, wi, onde:
1. M ′ escreve w na fita, após a entrada para M ′ ; suponha, então, que a fita fique
assim: hx[w ⊔ . . ., onde “h” é o sı́mbolo de inı́cio de fita para M ′ , x refere-se à
palavra de entrada para M ′ , e “[” faz o papel de sı́mbolo de inı́cio de fita para a
simulação de M no passo a seguir;
2. M ′ se comporta como M sobre [w ⊔ . . .;
3. na situação em que M para, M ′ se comporta como MX sobre hx ⊔ . . ..
Observe que
L(M ′ ) satisfaz P se e somente se M para ao processar w,
pois:
• Se M para ao processar w, L(M ′ ) = L(MX ); portanto, L(M ′ ) satisfaz P .
• Se M não para ao processar w, L(M ′ ) = ∅; dada a suposição inicial desse caso,
então L(M ′ ) não satisfaz P .
Dessa forma, conclui-se que {RhM i | L(M ) satisfaz P e ∅ não satisfaz P } não é recur-
siva.
Caso 2 ∅ satisfaz P . Nesse caso, ∅ não satisfaz ¬P . E como P não é trivial, ¬P
também não é trivial. Pela argumentação do caso 1, {RhM i | L(M ) satisfaz ¬P } não
é recursiva. Como essa linguagem é o complemento 11 de {RhM i | L(M ) satisfaz P } e
as linguagens recursivas são fechadas sob complementação,12 segue-se que a linguagem
11
É o complemento com relação ao conjunto das palavras da forma RhM i, que é recursivo.
12
Mesmo relativa a conjunto recursivo, como pode ser facilmente verificado.
Newton José Vieira Capı́tulo 2: Máquinas de estados finitos 263
Uma solução para um SCP S = (Σ, P ) é uma sequência finita de pares de P tal que
a palavra formada pela concatenação dos primeiros elementos dos pares seja idêntica
àquela formada pela concatenação dos segundos elementos dos mesmos pares. Observe
que cada par pode aparecer várias vezes na sequência. Segue uma definição mais formal.
Definição 66 Seja um SCP S = (Σ, [(x1 , y1 ), (x2 , y2 ), . . . , (xn , yn )]). Uma solução
para S é uma sequência i1 , i2 , . . . , ik tal que
x i1 x i2 . . . x ik = y i1 y i2 . . . y ik ,
onde 1 ≤ ij ≤ n para 1 ≤ j ≤ k.
Exemplo 121 Seja o SCP ({0, 1}, [(10, 0), (0, 010), (01, 11)]). Esse SCP tem três pa-
res: (x1 = 10, y1 = 0), (x2 = 0, y2 = 010) e (x3 = 01, y3 = 11) . Uma solução seria
a sequência 2131, pois x2 x1 x3 x1 = y2 y1 y3 y1 : 0 10 01 10 = 010 0 11 0. Para maior
clareza, pode ser conveniente apresentar cada par (xi , yi ) na forma xyii . Nesse caso, a
solução referida pode ser apresentada assim:
0 10 01 10
.
010 0 11 0
Além destas, quaisquer quantidades de justaposições da sequência anterior formam
soluções. Exemplos: 21312131, 213121312131 etc.
264 Editora Thomson Introdução aos fundamentos da computação
x 1 x i2 . . . x ik = y 1 y i2 . . . y ik ,
Exemplo 122 Seja o SCP ({0, 1}, [(0, 010), (10, 0), (01, 11)]), obtido do SCP do Exem-
plo 121 invertendo-se o primeiro e o segundo pares. Uma solução para esse SCP, que
satisfaz os requisitos do PCPM, seria: 1232.
Já o SCP do Exemplo 121, ({0, 1}, [(10, 0), (0, 010), (01, 11)]), não tem solução que
satisfaça os requisitos do PCPM, pois no primeiro par uma palavra começa com 1 e a
outra com 0.
• x′i o resultado de colocar “∗” após cada sı́mbolo de xi . Por exemplo, se xi = 11010,
então xi = 1 ∗ 1 ∗ 0 ∗ 1 ∗ 0∗.
• yi′ o resultado de colocar “∗” antes de cada sı́mbolo de yi . Por exemplo, se
yi = 0100, então yi = ∗0 ∗ 1 ∗ 0 ∗ 0.
Seja “#” um sı́mbolo não pertencente a Σ, e seja o SCP S ′ = (Σ ∪ {∗, #}, P ′ ), onde P ′
é constituı́do por n + 2 pares:
Newton José Vieira Capı́tulo 2: Máquinas de estados finitos 265
Será mostrado, conforme requerido, que S apresenta solução começada com (x1 , y1 ) se,
e somente se, S ′ tiver solução:
(→) Suponha que S tenha solução iniciada com (x1 , y1 ), e seja 1, i2 , . . . , ik uma solução
arbitrária de S, onde 1 ≤ ij ≤ n para 2 ≤ j ≤ k. Nesse caso, uma solução para S ′ seria
(mostrando-se os pares em vez de ı́ndices):
(←) Suponha que S ′ tenha solução. O único par de P ′ cujos elementos começam com o
mesmo sı́mbolo é (∗x′1 , y1′ ), e o único par de P ′ cujos elementos terminam com o mesmo
sı́mbolo é (#, ∗#). Assim, uma solução para S ′ só pode ter a forma
Além disso, existe uma solução dessa forma em que (∗x′1 , y1′ ) acontece apenas no inı́cio
e (#, ∗#) ocorre apenas no final. Assim,
x 1 x i2 x i3 xi
··· k
y 1 y i2 y i3 y ik
• ∆ = E ∪ Γ ∪ {∗, #};
266 Editora Thomson Introdução aos fundamentos da computação
Pode-se mostrar que M para ao processar w se, e somente se, o SCP S tem solução
iniciada com (∗, ∗hiw∗).
Exemplo 123 Seja a MT cujo diagrama de estados está representado na Figura 4.4b,
página 210, supondo o alfabeto de entrada como sendo {a, b}. A partir dela e da palavra
w = aab, pode-se construir, usando a técnica do Teorema 50, um SCP cujo primeiro
par é (∗, ∗h1aab∗) e os restantes são:
Uma solução para o SCP apresentado, espelhando uma computação de M com a palavra
aab, seria construı́da, passo a passo, assim:
Newton José Vieira Capı́tulo 2: Máquinas de estados finitos 267
• Colocam-se os pares (a, a), (b, b), (∗, ∗), (h, h) e (a, a):
∗h1aab ∗ ha
∗h1aab ∗ ha2ab ∗ ha
Exercı́cios
1. Para cada PD a seguir, mostre que o mesmo é decidı́vel:
3. Mostre que é decidı́vel ou que não é: dada uma MT M , determinar se a com-
putação de M percorre alguma transição da forma δ(e, a) = [e, b, d] (um laço),
quando a fita é iniciada em branco.
a) Pode-se usar o Teorema de Rice para mostrar que esse problema é inde-
cidı́vel? Justifique.
b) Reduza o problema da parada a este.
c) A linguagem Lx = {RhM i | x ∈ L(M )} é LRE? Justifique.
Para cada uma delas mostre que ela é LRE ou que não é.
8. Seja a MT M = ({A, B, C}, {0, 1}, {h, ⊔, 0, 1}, h, ⊔, δ, A), onde δ é dada por:
9. Prove que o PCP para SCPs com alfabeto de um único sı́mbolo é decidı́vel.
10. Dado um SCP S, seja L(S) a linguagem constituı́da de todas as soluções para
S. Ou seja, se S = (∆, P ), sendo P = [(x1 , y1 ), (x2 , y2 ), . . . , (xn , yn )], então
L(S) = {i1 i2 . . . ik | xi1 xi2 . . . xik = yi1 yi2 . . . yik }. Existe algoritmo que, dado um
SCP S arbitrário, seja capaz de produzir uma GLC G tal que L(G) = L(S)?
Px → xi Px si , para cada 1 ≤ i ≤ n, e
Px → xi si , para cada 1 ≤ i ≤ n.
RhSi R RhGx , Gy i
Py → yi Py si , para cada 1 ≤ i ≤ n, e
Py → yi si , para cada 1 ≤ i ≤ n.
Embora as LLCs não sejam fechadas sob complementação, o fato é que existem
GLCs para L(Gx ) e L(Gy ) (veja o Exercı́cio 3 no final desta seção, página 271). Com
base nisso, segue o próximo teorema.
Teorema 52 Não existe algoritmo para determinar se L(G) = Σ∗ , para uma GLC G
arbitrária.
Prova
O PCP pode ser reduzido a este, construindo-se uma GLC para L(Gx ) ∪ L(Gy ), pois:
pois:
Newton José Vieira Capı́tulo 2: Máquinas de estados finitos 271
Teorema 53 Não existe algoritmo para determinar se uma GLC arbitrária é ambı́gua.
Prova
O PCP pode ser reduzido a este, produzindo-se, a partir de um SCP S, a gramática
G = ({P, Px , Py }, Σ ∪ {s1 , s2 , . . . , sn }, Rx ∪ Ry ∪ {P → Px , P → Py }, P )
pois:
Exercı́cios
1. Mostre que é decidı́vel ou que não é:
a) Dados um conjunto finito F e uma GLC G, determinar se F ⊆ L(G);
b) Dadas uma GR R e uma GLC G, determinar se L(G) ⊆ L(R);
c) Dadas uma GR R e uma GLC G, determinar se L(R) ⊆ L(G);
d) Dada uma GR R, determinar se R é ambı́gua.
2. Construa as gramáticas Gx e Gy , como definidas no inı́cio da seção, correspon-
dentes ao SCP ({0, 1}, P ), onde P consta dos pares (01, 011), (001, 01), (10, 00).
3. Escreva uma gramática para a linguagem L(Gx ), onde Gx é a GLC definida no
inı́cio da seção.
4. Mostre que o seguinte problema é ou não decidı́vel: dadas uma GR GR e uma
GLC GL , determinar se L(GR ) ∩ L(GL ) = ∅.
5. Mostre que o seguinte problema é ou não decidı́vel: dadas duas GLCs G1 e G2 ,
cada uma com uma única variável, determinar se L(G1 ) ∩ L(G2 ) = ∅.
6. Mostre que o seguinte problema não é decidı́vel: dadas duas GLCs G1 e G2 ,
determinar se L(G1 ) ∩ L(G2 ) é finito.
7. Mostre que o seguinte problema não é decidı́vel: dada uma GLC G, determinar
se L(G) é finito.
8. Mostre que são indecidı́veis os problemas de se determinar, dadas duas GLCs G1
e G2 , que:
a) L(G1 ) = L(G2 );
b) L(G1 ) ⊆ L(G2 ).
272 Editora Thomson Introdução aos fundamentos da computação
• V é um alfabeto de variáveis;
• ΣN é um alfabeto de não terminais, disjunto de V;
• ΣT é um alfabeto de terminais, disjunto de ΣN e de V;
• R é um conjunto finito de regras; e
• A é um subconjunto finito de (ΣN ∪ ΣT )∗ cujos elementos são chamados
axiomas.
x0 z0 z1 x1 . . . zn−1 xn ⇒ v ′
Por exemplo, sendo P = ({X}, ∅, {a, b}, {X → aXb}, {λ}), tem-se que L(P ) =
{an bn | n ≥ 0}, pois:
λ ⇒ ab ⇒ aabb ⇒ · · · ⇒ an bn .
M1 : h ···
✻
distância atual: 8
M2 : h ···
✻
(O conteúdo das fitas não é mostrado por ser irrelevante.)
7. Mostre que o PCP para SCPs com alfabeto de dois sı́mbolos é indecidı́vel. Para
isso, reduza o PCP a este problema.
8. Conclua a prova do Teorema 50, isto é, mostre que M para ao processar w se, e
somente se, o SCP S tem solução iniciada com (∗, ∗hiw∗).
9. Um sistema semi-Thue é um par S = (Σ, R), em que Σ é um alfabeto e R é um
conjunto de regras da forma u → v, onde u ∈ Σ+ e u ∈ Σ∗ . Seja o seguinte
problema associado a sistemas semi-Thue:
274 Editora Thomson Introdução aos fundamentos da computação
10. Seja Gx uma GLC obtida como mostrado no inı́cio da Seção 5.6, página 269.
Descreva APs para reconhecer:
a) L(Gx );
b) L(Gx ).