Linguagens Formais e Autômatos - Leandro Dionízio - Aula 05 MaquinaTuring

Prévia do material em texto

Linguagens Formais
Leandro Dionízio Ramos
1
Máquina Turing
• Um sistema formal pode ser visto como uma 
espécie de jogo rigorosamente definido, que 
especifica regras para manipulação de 
símbolos.
• Um sistema formal é semelhante às regras 
dispostas para um determinado jogo.
2
Máquina Turing
• Para dizer a alguém como jogar e para estabelecer as 
regras que qualificam um sistema formal, três 
aspectos desse “jogo” devem ser estabelecidos: 
– Natureza dos símbolos;
– Descrição da situação inicial do jogo;
– Lista de quais movimentos são permitidos a uma 
dada posição.
3
Máquina Turing
• Alain Turing (1912-1954) foi um brilhante 
matemático, em Cambridge, Inglaterra, numa época 
efervescente de desenvolvimento da lógica e da 
matemática que haveria de resultar no computador 
digital, os anos 30 e 40 do século passado. 
• É geralmente considerado como o fundador das 
ciências da computação.
4
Máquina Turing
• A máquina de Turing é um autómato, com uma 
unidade de controle e com um dispositivo especial 
que funciona simultaneamente como entrada, 
armazenamento, e saída.
• Esse dispositivo é uma fita unidimensional que 
contém um número ilimitado de células cada uma 
das quais pode conter um único símbolo.
5
Máquina Turing
• A fita da MT prolonga-se indefinidamente em ambos 
os sentidos e por isso pode conter uma quantidade 
infinita de informações. Estas informações podem 
ser lidas e alteradas em qualquer ordem e daí o 
potencial da MT.
• Associada à fita está uma cabeça de leitura-escrita 
que se pode mover sobre a fita para a esquerda ou 
para a direita, podendo escrever ou ler um único 
símbolo em cada movida.
6
Máquina Turing
• É constituída por três partes:
– Fita: 
Usada simultaneamente como dispositivo de entrada, de 
saída e de memória do trabalho;
– Unidade de Controle: 
Reflete o estado corrente da máquina. Possui uma unidade 
de leitura e gravação (cabeça da fita), a qual acessa uma 
célula da fita de cada vez e movimenta-se para a esquerda 
ou para a direita;
7
Máquina Turing
• É constituída por três partes:
– Programa ou Função de Transição: 
Função que define o estado da máquina e comanda as 
leituras, as gravações e o sentido de movimento da cabeça 
da fita.
8
Máquina Turing
9
Máquina Turing
• A unidade de controle possui um número pré-
definido de estados. 
• A cabeça da fita lê o símbolo de uma célula de cada 
vez e grava um novo símbolo. 
• Após a leitura/gravação (a gravação é realizada na 
mesma célula de leitura), a cabeça move uma célula 
para a direita ou para a esquerda. 
• O símbolo gravado e o sentido do movimento são 
definidos pelo programa.
10
Máquina Turing
• Uma máquina de Turing M é definida pelo sétupla:
– M= (Q, Σ, Γ, δ , q0, , F):
• Q - conjunto de estados possíveis da máquina
• Σ - alfabeto de entrada
• Γ - conjunto finito alfabeto da fita
• δ - função de transição
• q0 - estado inicial
• - símbolo especial chamado de branco, ( ∈ Γ)
• F - conjunto de estados finais (aceitadores)
11
Máquina Turing
• O alfabeto de entrada é igual ao alfabeto da fita, com 
exceção do símbolo (branco), Portanto:
– Σ = Γ -
• A função de transição é em geral uma função parcial em 
Q x Γ
– δ: Q x Γ Q x Γ {R, L}
• R significa movida para a direita e L movida para a 
esquerda. 
12
Máquina Turing
• Os dois argumentos de entrada da função de transição e 
os três de saída são os seguintes:
• A movida da cabeça faz-se depois da escrita do novo 
símbolo na fita.
13
Máquina Turing
• Exemplo:
• Sejam: 
– Σ = { a, b }
– Γ = { a, b, }
– δ: (Q x Γ) (Q x Γ x {R, L})
• Transição:
• δ: ( q0, a ) = ( q1, b, R )
14
Máquina Turing
• O autómato é inicializado (no estado inicial q0 ) com 
alguma coisa já escrita na fita.
• Executa depois uma sequência de operações, uma 
computação, definidas pela função δ.
15
Máquina Turing
• Como δ é uma função parcial, pode chegar a uma 
configuração para a qual não está definida nenhuma 
transição. O autómato fica então no estado parado.
• Nunca se definem transições a partir dos estados 
finais e por isso uma máquina de Turing para sempre 
que atinge um estado final.
16
Máquina Turing
• Exemplo:
Seja a máquina de Turing definida por:
• Transições:
17
Máquina Turing
18
Máquina Turing
19
Máquina Turing
• A aceitação de uma cadeia pela Máquina de Turing 
acontece quando o estado final é atingido 
independente de onde a cabeça está na fita. 
• Se a Máquina de Turing pára em algum estado não 
final ou simplesmente entrar em “loop” infinito, 
então a cadeia não é aceita.
20
Máquina Turing
• Exemplo:
• Dados dois números positivos x e y. Construa uma 
Máquina de Turing que calcule x + y.
• Seja x = |z(x)| com z(x) ∈ {1}*, ou seja, o número será 
representado pela quantidade de dígitos 1 (por exemplo, 
3 = 111).
• seja 5 + 3, então w = {111110111}
• Desenhe a MT
21
Máquina Turing
22
Máquina Turing
• Exemplo:
Considere a linguagem: MT = {ܽ௡	+	ܾ௡	| n ≥ 0}, construa 
uma Máquina de Turing para essa linguagem.
• Passo 1: Construir o Grafo da Máquina de Turing
• Passo 2: Construir sua Tabela de Transição
• Passo 3: Escrever os elementos da Máquina de Turing
23
Máquina Turing
• O algoritmo apresentado reconhece o primeiro símbolo 
a, o qual é marcado como A, e movimenta a cabeça da 
fita à direita, procurando o b correspondente, o qual é 
marcado como B. Este ciclo é repetido sucessivamente 
até identificar para cada a o seu correspondente b. 
• Adicionalmente, o algoritmo garante que qualquer outra 
palavra que não esteja na forma {ܽ௡	+	ܾ௡}	seja 
rejeitada.
24
Máquina Turing
25
- Início da fita
β – Também 
conhecido como 
branco. 
Máquina Turing
26
Máquina Turing
27
Sequência aabb
Máquina Turing
• Exercício
• Considere a Máquina de Turing vista em aula. 
Verifique qual o estado final após a computação para 
as seguintes palavras:
– ab
– aba
– aaba
– aaabbb
28