Máquina de Turing

Prévia do material em texto

Como funciona a máquina de Como funciona a máquina de 
TuringTuring
 
Máquina de Turing
- A máquina de Turing possui uma memória linear 
infinita chamada de FITA.
- Possui um formalismo reconhecedor.
- A grande diferença das máquinas de Turing é 
que a fita não é usada apenas para a leitura, mas 
também para a escrita.
 
Máquina de Turing
Fita
◦ Inicialmente, recebe a palavra a ser 
reconhecida.
◦ Limitada à esquerda.
 - Representação do início da fita: $
◦ Infinita à direita
 - Símbolos brancos β, após a palavra.
◦ Pode ser lida ou escrita uma posição por vez
 - Possui um alfabeto (símbolos terminais)
◦ Após uma operação, anda uma posição :
 - Para a Esquerda ou Direita
Não pode ir para a esquerda se estiver em $.
 
Máquina de Turing
Fita
- Cada posição da fita guarda um símbolo.
- Os símbolos são lidos em sequência, um por 
vez pelo cabeçote.
- A palavra ser reconhecida é automaticamente 
gravada na fita na inicialização da máquina.
- Como a fita é infinita, as posições mais a direita 
e mais a esquerda da palavra são preenchidas 
com símbolos brancos ( [] )
 
Máquina de Turing
Fita
- Então se considerarmos a palavra abab como 
palavra de entrada na máquina, a fita deverá ficar 
assim.
 
 
Máquina de Turing
Função de transição
◦ Recebe como entrada
- O estado atual
- O símbolo da posição atual
◦ Resultados
- O próximo estado
- Símbolo a ser gravado
- Direção do movimento da fita
 D: direita
 E: esquerda
 
Máquina de Turing
- A máquina de Turing realiza 3 ações por etapa
 1 - Ela lê o símbolo na fita
 2 - Ela reescreve o símbolo fazendo uma 
substituição, muitas vezes ela reescreve 
colocando o mesmo símbolo atual deixando a 
posição na fita sem efetiva alteração
 3 - E move o cabeçote para a esquerda ou para 
a direita
 
Máquina de Turing
Cada transição tem o seguinte rótulo : Y / X, M
Y = É o símbolo lido na fita.
X = É o símbolo pelo qual Y deve ser substituído
M = É a direção que o cabeçote deve ir (E ou D)
 
Máquina de Turing
Exemplo da máquina de Turing utilizando o 
alfabeto {a,b}
 
Máquina de Turing
- A palavra não precisa ser lida por inteiro para 
ser aceita, apenas o que importa é que a 
máquina pare em um estado de aceitação, 
seguindo o exemplo anterior, esta máquina então 
deveria parar no estado q1.
 
Máquina de Turing
- Mãos à obra … ou melhor … máquina à obra, 
vamos olhar se a palavra aab é reconhecida por 
esta máquina de Turing.
 
Máquina de Turing
- A máquina de Turing pode ser definifda com 
uma 7-tupla, usando a descrição abaixo : 
 
Máquina de Turing
- Seguindo o exemplo anterior :
 
 
Em memória de Alan Turing 
1912-1954
Equipe : 
Thalia Lisboa 
Samuel Rodrigues 
Elmo Victor
	Slide 1
	Slide 2
	Slide 3
	Slide 4
	Slide 5
	Slide 6
	Slide 7
	Slide 8
	Slide 9
	Slide 10
	Slide 11
	Slide 12
	Slide 13
	Slide 14