tc

Mateus Alves
October 2025

1 Introduction
Exercı́cio 1 – Sequência de Configurações de uma
Máquina de Turing
Seja a máquina

M = ({q1 , q2 , q3 , q4 , q5 , qa , qr }, {0}, {0, x, ⊔}, δ, q1 , qa , qr )

definida pela função de transição:

δ 0 x ⊔
q1 (q2 , ⊔, D) (qr , x, D) (qr , ⊔, D)
q2 (q3 , x, D) (q2 , x, D) (qa , ⊔, D)
q3 (q4 , 0, D) (q3 , x, D) (q5 , ⊔, E)
q4 (q3 , x, D) (q4 , x, D) (qr , ⊔, D)
q5 (q5 , 0, E) (q5 , x, E) (q2 , ⊔, D)
—

(a) Entrada: 0

q1 0 ⇒ ⊔q2 ⊔ ⇒ ⊔ ⊔ qa ⊔

Aceita.

(b) Entrada: 00

q1 00 ⇒ ⊔q2 0 ⇒ ⊔xq3 ⊔ ⇒ ⊔q5 x

⇒ q5 ⊔ x ⇒ ⊔q2 x ⇒ ⊔xq2 ⊔
⇒ ⊔x ⊔ qa ⊔

1
 Aceita.

(c) Entrada: 000

q1 000 ⇒ ⊔q2 00 ⇒ ⊔xq3 0 ⇒ ⊔x0q4 ⊔

⇒ ⊔x0 ⊔ qr ⊔

Rejeita.

(d) Entrada: 0000

q1 0000 ⇒ ⊔q2 000 ⇒ ⊔xq3 00 ⇒ ⊔x0q4 0

⇒ ⊔x0xq3 ⊔ ⇒ ⊔x0q5 x ⇒ ⊔xq5 0x
⇒ ⊔q5 x0x ⇒ q5 ⊔ x0x ⇒ ⊔q2 x0x
⇒ ⊔xq2 0x ⇒ ⊔xxq3 x ⇒ ⊔xxxq3 ⊔
⇒ ⊔xxq5 x ⇒ ⊔xq5 xx ⇒ ⊔q5 xxx
⇒ q5 ⊔ xxx ⇒ ⊔q2 xxx ⇒ ⊔xq2 xx
⇒ ⊔xxq2 x ⇒ ⊔xxxq2 ⊔ ⇒ ⊔xxx ⊔ qa ⊔

Aceita.

Conclusão

Entrada Resultado
0 Aceita
00 Aceita
000 Rejeita
0000 Aceita
—
Observação: a máquina marca cada sı́mbolo 0 como x, varre até o fim da
cadeia, volta e repete o processo. Ela aceita quando o número de blocos de zeros
é par e rejeita quando é ı́mpar (exceto o caso de uma única célula).

2
Exercı́cio 2 – Máquinas de Turing que decidem
linguagens
Notação: sı́mbolos de marcação X, Y, Z são usados para indicar letras já pro-
cessadas. A fita contém apenas {a, b, c, ⊔}; os estados de aceitação e rejeição
são qacc e qrej .
—

(a) L1 = {ai bj ck | 0 ≤ i ≤ j ≤ k}
Ideia: verificar que a cadeia tem forma a∗ b∗ c∗ e que cada a possui um b corre-
spondente e cada b possui um c correspondente.
Algoritmo:
1. Verifique a forma a∗ b∗ c∗ ; se violada, rejeite.

2. Para cada a não marcado: marque a → X, procure o primeiro b não

marcado; se não existir, rejeite; marque b → Y ; volte ao inı́cio.
3. Após não restarem a não marcados, emparelhe cada b não marcado com
um c não marcado (marcando b → Y, c → Z).
4. Aceite se todos os b foram emparelhados com algum c.

Estados principais: qcheck , qab , qf indB , qbc , qf indC , qacc , qrej .

—

(b) L2 = {ai bj ck | i + j = k, i, j, k > 0}

Ideia: cada a e cada b consome exatamente um c. No fim não deve restar
sı́mbolo não marcado.
Algoritmo:
1. Verifique a forma a∗ b∗ c∗ e a presença de ao menos um a, b, c.

2. Para cada a não marcado, marque a → X e um c não marcado c → Z; se

faltar c, rejeite.
3. Repita o mesmo para cada b não marcado.
4. Se todos os a, b têm c correspondente e nenhum sı́mbolo sobra, aceite.

3
(c) L3 = {ai bj ck | i ̸= j ̸= k, i, j, k > 0}
Ideia: os três contadores devem ser distintos entre si. A máquina executa três
sub-rotinas de comparação: (i=j?), (j=k?) e (i=k?). Se qualquer comparação
der igualdade, rejeite; caso contrário, aceite.
Cada sub-rotina emparelha sı́mbolos dos dois blocos (marcando-os) e testa
se terminam simultaneamente.
—

(d) L4 = {w ∈ {a, b}∗ | wnãoédaf ormaan bn }

Ideia: é o complemento de an bn . Basta construir a MT que decide an bn e
inverter aceitação/rejeição.
Submáquina Meq para an bn : marque o primeiro a → X, procure o
primeiro b → Y ; se não encontrar, rejeite; repita até acabar; aceite se não
sobrar a ou b. A máquina de L4 troca qacc ↔ qrej .
—

(e) L5 = {w ∈ {a, b}∗ | #a(w) = #b(w)}

Ideia: em qualquer ordem, o número de a’s é igual ao de b’s.
Algoritmo:
1. Se existir a não marcado, marque a → X e procure um b não marcado
b → Y ; se não existir, rejeite.
2. Repita simetricamente para b não marcado.
3. Quando não restarem sı́mbolos não marcados, aceite.
—

(f ) L6 = {w ∈ {a, b}∗ | #a(w) = 2 · #b(w)}

Ideia: cada b corresponde a dois a’s.
Algoritmo:
1. Enquanto existir b não marcado: marque b → Y ; procure dois a’s não
marcados e marque a → X; se não achar dois, rejeite.
2. No fim, se não restar a não marcado, aceite; caso contrário, rejeite.
—

(g) L7 = {w ∈ {a, b}∗ | #a(w) < 2 · #b(w)}

Ideia: adaptar a rotina anterior. Durante o emparelhamento de cada b com
dois a’s, se faltar a em algum momento, aceite imediatamente (pois #a < 2#b).
Se todos os b obtiverem dois a’s, rejeite.
—

4
(h) L8 = {w ∈ {a, b}∗ | wépalı́ndromoe#a(w) = #b(w)}
Ideia: interseção de duas linguagens decidı́veis:
1. Verifique se w é palı́ndromo: compare primeiro e último sı́mbolo, marcando-
os; repita até o centro.
2. Se for palı́ndromo, execute a rotina de L5 para checar igualdade de con-
tagens.
3. Aceite apenas se ambos os testes forem verdadeiros.
—

(i) L9 = {w#t | w, t ∈ {a, b}∗ , wésubcadeiadet}

Ideia: verificar se t contém w como substring.
1. Separe as partes w e t.
2. Para cada posição possı́vel em t, compare w sı́mbolo a sı́mbolo com o
trecho correspondente de t.
3. Se algum casamento completo ocorrer, aceite; se o fim de t for atingido
sem sucesso, rejeite.
Estados tı́picos: qinit , qcmp , qrestore , qshif t , qacc , qrej .
—

(j) L10 = {ww | w ∈ {a, b}∗ }

Ideia: verificar se a palavra é composta por duas metades idênticas.
Algoritmo:
1. Calcule o comprimento total m; para cada n ≤ m/2, teste se m = 2n.
2. Marque os n primeiros sı́mbolos (X) e os n últimos (Y ). Compare-os um
a um, movendo a cabeça entre as extremidades.
3. Se todas as comparações coincidirem e não restarem sı́mbolos extras,
aceite; caso contrário, rejeite.
Observação: a MT pode testar todos os possı́veis pontos de corte, ou copiar
a primeira metade para uma área auxiliar e comparar.
—
Conclusão: Cada uma das linguagens L1 , . . . , L10 é decidı́vel. As con-
struções acima descrevem como obter os diagramas completos de estados de
suas respectivas Máquinas de Turing. [a4paper,11pt]article [utf8]inputenc ams-
math,amssymb tikz automata,positioning,[Link]
Exercı́cio 3 – Subrotinas de Máquina de Turing
Notação: escrevemos transições como δ(q, a) = (q ′ , b, D) (D = direita, E =
esquerda). O branco é ⊔.

5
Subrotinas (a) a (h)
(a) TESTE-INICIO
Descrição: aceita se a cabeça já está na posição mais à esquerda da fita (i.e.,
o sı́mbolo atual está imediatamente após infinitos brancos à esquerda). Rejeita
caso contrário.
Ideia: mover-se uma posição para a esquerda; se encontrará ⊔ então a
cabeça não estava no inı́cio (volte e rejeite). Se ao mover para a esquerda já
estava em ⊔ (isto é, o sı́mbolo atual era o primeiro não-branco), então voltamos
e aceitamos.
Máquina (esquemática):
• q0 : estado inicial (a cabeça está sobre o sı́mbolo atual).
• qL : move uma célula à esquerda para checar.
• qacc , qrej : aceitação/rejeição.

Transições principais:

δ(q0 , a) = (qL , a, E) paratodoa ∈ Γ.

δ(qL , ⊔) = (qacc , ⊔, D) (achoubrancoàesquerda : estavanoinı́cio).
δ(qL , b) = (qrej , b, D) paratodob ̸= ⊔ (hásı́mboloàesquerda).

(b) RESET
Descrição: desloca a cabeça até a posição mais à esquerda da fita (primeiro
sı́mbolo não-blank) e termina em estado de aceitação com a cabeça sobre esse
primeiro sı́mbolo.
Ideia: mover-se repetidamente para a esquerda até encontrar ⊔, então mover
uma posição à direita (para o primeiro sı́mbolo) e aceitar.
Transições principais:

δ(q0 , a) = (qL , a, E) ∀a.

δ(qL , ⊔) = (qr , ⊔, D)
δ(qr , a) = (qacc , a, N ) (N = nãomover/estadof inal).

(Usa-se qr para posicionar sobre o primeiro sı́mbolo não-branco e então aceita.)

6
(c) LIMPAR
Descrição: limpa (coloca brancos) todas as células desde a posição atual até a
posição mais à esquerda (inclusive ou exclusiva conforme enunciado — aqui as-
sumimos exclusive da posição atual: limpa as células à esquerda até o primeiro
não-blank à esquerda). Pelo enunciado de exemplo, a posição atual e os sı́mbolos
à esquerda até o inı́cio ficam em branco, e a cabeça termina no inı́cio, em qa .
Ideia: iterativamente escrever ⊔ na célula atual, mover-se à esquerda e
repetir até encontrar a célula que já é branca (ou até o começo), então aceitar.
Transições principais:
δ(q0 , a) = (qc , ⊔, E) ∀a ̸= ⊔.
δ(qc , b) = (qc , ⊔, E) ∀b ̸= ⊔.
δ(qc , ⊔) = (qacc , ⊔, D).

(d) LIMPAR-R
Descrição: limpa da posição atual até o primeiro branco à direita (i.e., substitui
por ⊔ cada célula desde a atual até encontrar o primeiro ⊔ à direita), e termina
em qa com a cabeça sobre o primeiro branco (ou sobre a célula seguinte, conforme
exemplo).
Ideia: escreva ⊔ na célula atual, mova à direita; se encontrar sı́mbolo não-
branco repita; se encontrar ⊔, pare e aceite.
Transições principais:
δ(q0 , a) = (qr , ⊔, D) ∀a ̸= ⊔.
δ(qr , b) = (qr , ⊔, D) ∀b ̸= ⊔.
δ(qr , ⊔) = (qacc , ⊔, N ).

(e) SHIFT-L
Descrição: desloca a subcadeia iniciada na posição atual uma posição para a
esquerda. Ex.: se a fita a partir da cabeça é s0 s1 s2 · · · ⊔ · · ·, após SHIFT-L
fica s0 s1 s2 · · · (onde “ ” representa a célula anterior preenchida por aquilo que
havia antes, normalmente ⊔).
Ideia (rotina clássica):
1. Salve o sı́mbolo atual (marcando-o com um marca especial ou movendo-o
para uma área de trabalho).
2. Mova para a célula imediatamente à esquerda, escreva o sı́mbolo salvo
lá, e então vá para a célula da direita (original) e continue copiando
sı́mbolos um a um: ler si , apagar (ou marcar), escrever em posição ante-
rior, avançar.

7
 3. Ao encontrar o primeiro ⊔ (final da subcadeia), escreva ⊔ na última
posição remanescente e aceite.
Descrição em estados (esquemática): Estados: q0 (inı́cio), q save (guardar
sı́mbolo e mover esquerda), q copy (copiar em loop), q f inish.
Transições essenciais (esquemático):
δ(q0 , a) = (q save, X, E) (marqueaporXeváesquerda),
δ(q save, b) = (q copy, b, D) (escreveb= sı́mbolosalvo),
δ(q copy, c) = (q copy, X, D) (marcaremovercopiando),
δ(q copy, ⊔) = (q f inish, ⊔, E).

(A implementação completa usa marcas para lembrar sı́mbolo salvo; é longa

mas direta.)

(f ) SHIFT-R
Descrição: desloca a subcadeia iniciada na posição atual uma posição para a
direita.
Ideia: procedimento análogo ao SHIFT-L, porém trabalhando da direita
para a esquerda para evitar sobrescrever dados — primeiro encontre o fim da
subcadeia, copie sı́mbolos para a direita um a um voltando para a esquerda, etc.
Estrutura de estados (esquemática): q0 → q f indEnd → q copyLef tT oRight →
q f inish.
Observação: a rotina tipicamente:
• localiza o fim da subcadeia (primeiro ⊔);
• move-se uma célula à esquerda e começa a copiar sı́mbolos para a direita
(escrevendo em células em branco);
• marca sı́mbolos copiados para evitar duplicação e volta para continuar;
• ao terminar, limpa marcas e aceita.

(g) COPIA
Descrição: copia a subcadeia iniciada na posição atual para a primeira área
em branco à direita (por exemplo, coloca um separador # e escreve a cópia).
Ideia: usar algoritmo de copiar que:
1. Percorre o bloco original da esquerda para a direita, marcando cada sı́mbolo
lido (por exemplo 0 → X, 1 → Y ).
2. Para cada sı́mbolo marcado, move-se até o final (primeiro ⊔) e escreve o
sı́mbolo correspondente, depois retorna ao próximo sı́mbolo não marcado
do bloco original.

8
 3. Após terminar, restaura marcas no bloco original ao sı́mbolo original.
Estados esquemáticos: q0 (inı́cio), q mark (marcar e lembrar sı́mbolo),
q write (ir ao fim e escrever), q return (voltar ao próximo).
Transições principais (exemplo para alfabeto {0, 1}):

δ(q0 , 0) = (q mark, X, D), δ(q 0, 1) = (q mark, Y, D).

δ(q mark, a) = (q mark, a, D) (iratéof im).
δ(q mark, ⊔) = (q write, a, E) (escrevesı́mbolosalvoevolta).

(Implementação completa precisa de estados separados para lembrar se o sı́mbolo

era 0 ou 1.)

(h) COPIA-D (cópia delimitada)

Descrição: copia a subcadeia indicada por delimitadores (por exemplo entre
“<” e “¿”) para a área em branco à direita, preservando delimitadores e adicio-
nando a cópia após eles.
Ideia: varrer do delimitador de inı́cio, marcar sı́mbolos até o delimitador de
fim; para cada sı́mbolo marcado, ir ao fim e escrever sua cópia; depois restaurar
marcas; por fim escrever “#”+cópia (ou apenas a cópia, conforme enunciado).
Estados esquemáticos: muito semelhante à subrotina COPIA, mas começa
ao encontrar “<” e termina ao encontrar “¿ ”.

Diagramas compactos (alguns exemplos com tikz)

(a) TESTE-INICIO (diagrama)

[¿=Stealth,shorten ¿=1pt,auto,node distance=2.2cm] [state,initial] (q0) q0 ;

[state] (qL) [right=of q0] qL ; [state,accepting] (qa) [right=of qL] qacc ; [state]
(qr) [below=of qL] qrej ; [-¿] (q0) edge node (a) → (qL , a, E) (qL) (qL)
edge[bend left] node ⊔ → (qacc , ⊔, D) (qa) (qL) edge[bend right] node
(b ̸= ⊔) → (qrej , b, D) (qr);

(b) RESET (diagrama)

[¿=Stealth,shorten ¿=1pt,auto,node distance=2.2cm] [state,initial] (q0) q0 ;

[state] (qL) [right=of q0] qL ; [state] (qr) [right=of qL] qr ; [state,accepting] (qa)
[right=of qr] qacc ; [-¿] (q0) edge node (a) → (qL , a, E) (qL) (qL) edge node
⊔ → (qr , ⊔, D) (qr) (qr) edge node (a) → (qacc , a, N ) (qa);

9
(d) LIMPAR-R (diagrama)

[¿=Stealth,shorten ¿=1pt,auto,node distance=2.2cm] [state,initial] (q0) q0 ;

[state] (qr) [right=of q0] qr ; [state,accepting] (qa) [right=of qr] qacc ; [-¿] (q0)
edge node (a ̸= ⊔) → (qr , ⊔, D) (qr) (qr) edge[bend left] node
(b ̸= ⊔) → (qr , ⊔, D) (qr) (qr) edge node ⊔ → (qacc , ⊔, N ) (qa);

Os outros subdiagramas (SHIFT-L, SHIFT-R, COPIA, COPIA-D) são maiores

mas seguem a mesma ideia:

• marcar sı́mbolo, mover até área de escrita, escrever, e voltar;

• usar estados para lembrar qual sı́mbolo foi marcado (uma cadeia de estados
por sı́mbolo do alfabeto).

Observações finais
• Apresentei cada subrotina com a ideia e as transições essenciais; cada uma
pode ser expandida para o diagrama de estados completo (detalhando um
estado por situação de guardar sı́mbolo X, retornar, restaurar marca, etc.).

• Se quiser, eu posso:
1. gerar o diagrama completo em TikZ para uma subrotina es-
pecı́fica (por exemplo COPIA ou SHIFT-L), com todos os estados
e todas as transições explı́citas; ou
2. fornecer a tabela completa de δ (linha-por-linha) para uma das
subrotinas.

10