Turing
Arquitetura de MT
Fita de Leitura / Escrita
〈
a1 a2 ...
ai
Controle
+
δ
... an
Registrador de Estado Atual e Máquina de Turing Determinística
Uma MTD é uma óctupla M = (Q, Σ, Γ, 〈, □, δ, i, F) em que:
- Q = conjunto de estados
- Σ = alfabeto de entrada
- Γ = alfabeto da fita ( Σ ⊂ Γ )
- 〈 = representa o primeiro símbolo da fita ( 〈 ∈ Γ − Σ )
- □ = representa o símbolo branco ( □ ∈ Γ − Σ, □ ≠ 〈 )
- δ = função de transição parcial Q × Γ → Q × Γ × { E, D}
- i = estado inicial
- F = conjunto de estados finais
Representação de uma transição : δ(e, a) = [ e´, b, d ]
e
a/bd
e´
Representação Gráfica
Ex.
0/0 E
1/1 E
0/1 D
1/0 D
□/□ E
〈/〈 D
Configuração Instantânea
C.I. de uma MTD é dada pela dupla [ e, x a y ] em que :
- e ∈ Q é o estado atual
- x ∈ Γ* é a palavra à esquerda da cabeça de leitura/escrita
- a ∈ Γ é o símbolo sob a cabeça de leitura/escrita
- y ∈ Γ* é a palavra à direita da cabeça de leitura/escrita
Linguagem Reconhecida por uma MTD
Seja uma MTD M = (Q, Σ, Γ, 〈, □, δ, i, F) então a linguagem reconhecida por M é :
L(M) = {w ∈ Σ* | [i, 〈 w]
[e, x a y], e ∈ F, δ(e,a) é indefinido}
*
Y/Y D
0/X D
1/Y E
X/X D
□/□
Y/Y D
Y/YE
0/0 E
Y/YD
0/0 D
Ex. L = { 0n1n | n ≥ 1}
E
Ex. L = { w ∈ {a, b}* | w = wR, | w | mod 2 = 0 } a/a D b/b D
□/□ E a /□
a/
D
□
E
a/a E b/b E
□/□ D
b
D
/□
/□
E
b
□/□ E a/a D b/b D
Ex. L = {a, b, c}* − ({a, b}{a, b, c}*) a/a D
a/a D b/b E b/b E
Linguagem Recursivamente Enumerável
⇒ Existe uma MT que a reconhece
Linguagem Recursiva
⇒ Existe uma MT que a reconhece e que pare para todas as palavras do alfabeto de entrada
Linguagem Reconhecida por uma MTD M = (Q, Σ, Γ, 〈, □, δ, i, F)
• Por Parada e Estado Final
L(M) = {w ∈ Σ* | [i, 〈 w]
• Por Estado Final
LF(M) = {w ∈ Σ* | [i, 〈 w]
*
*
a/a D
□/□
• Por Parada
LP(M) = {w ∈ Σ*