Exercícios sobre Máquina de Turing

Teoria da Computação Aula 11 Exercícios e variantes da Máquina de Turing Prof Alex Torquato Souza Carneiro alexcarneirofaculdadeimpactacombr Verificar se uma string de tamanho desconhecido e composta por símbolos do alfabeto A 0 1 termina em 1 Exercício 1 2 1 Verificar se uma string de tamanho desconhecido e composta por símbolos do alfabeto A 0 1 termina em 1 Exercício 1 3 1 Elemento após o último símbolo da string Verificar se uma string de tamanho desconhecido e composta por símbolos do alfabeto A 0 1 termina em 1 Exercício 1 4 1 Simulando o comportamento de uma Máquina de Turing Exercício 1 5 0 1 1 0 1 0 1 0 1 Controle Exercício 1 6 0 1 1 0 1 0 1 0 1 Controle Exercício 1 7 0 1 1 0 1 0 1 0 1 Controle Exercício 1 8 0 1 1 0 1 0 1 0 1 Controle Exercício 1 9 0 1 1 0 1 0 1 0 1 Controle Exercício 1 10 0 1 1 0 1 0 1 0 1 Controle Exercício 1 11 0 1 1 0 1 0 1 0 1 Controle Exercício 1 12 0 1 1 0 1 0 1 0 1 Controle Exercício 1 13 0 1 1 0 1 0 1 0 1 Controle Exercício 1 14 0 1 1 0 1 0 1 0 1 Controle Exercício 1 15 0 1 1 0 1 0 1 0 1 Controle String é aceita Verificar se uma string de tamanho desconhecido e composta por símbolos do alfabeto A 0 1 termina em 1 Exercício 1 16 q0 q2 q1 1 R 0 R Verificar se uma string de tamanho desconhecido e composta por símbolos do alfabeto A 0 1 termina em 1 Exercício 1 17 q0 q2 q1 1 R 0 R 1 R 0 R Verificar se uma string de tamanho desconhecido e composta por símbolos do alfabeto A 0 1 termina em 1 Exercício 1 18 q0 q2 q1 1 R 0 R 1 R 0 R 1 R 0 R Verificar se uma string de tamanho desconhecido e composta por símbolos do alfabeto A 0 1 termina em 1 Exercício 1 19 q0 q2 q1 qaceita 1 R 0 R 1 R 0 R R 1 R 0 R Verificar se uma string de tamanho desconhecido e composta por símbolos do alfabeto A 0 1 termina em 1 Exercício 1 20 q0 q2 q1 qrejeita qaceita 1 R 0 R 1 R 0 R R R 1 R 0 R Verificar se uma string s pertence à linguagem L anbn n 0 Exercício 2 21 a a a b b b Verificar se uma string s pertence à linguagem L anbncm n 0 e m 0 Exercício 3 22 a a a b b b c Verificar se uma string s pertence à linguagem L anbncn n 0 Exercício 4 23 a a b b c c Verificar se uma string s pertence à linguagem L wcw w ab Exercício 5 24 w1 w2 w3 c w1 w2 w3 Verificar se uma string s pertence à linguagem L wcw w ab Exercício 5 25 a a b c a a b Variantes da Máquina de Turing Definição da Máquina de Turing Máquina de Turing 27 Definição da Máquina de Turing Q 𝚺 𝚪 𝛅 q0 qaceitação qrejeição Máquina de Turing 28 Definição da Máquina de Turing Q 𝚺 𝚪 𝛅 q0 qaceitação qrejeição Q conjunto de estados 𝚺 alfabeto sem contar o espaço em branco 𝚪 alfabeto da fita incluindo o espaço em branco 𝛅 Q x 𝚪 Q x 𝚪 x L R função de transição q0 estado inicial qaceitação estados de aceitação qrejeição estados de rejeição Máquina de Turing 29 Definição da Máquina de Turing Q 𝚺 𝚪 𝛅 q0 qaceitação qrejeição Q conjunto de estados 𝚺 alfabeto sem contar o espaço em branco 𝚪 alfabeto da fita incluindo o espaço em branco 𝛅 Q x 𝚪 Q x 𝚪 x L R função de transição q0 estado inicial qaceitação estados de aceitação qrejeição estados de rejeição Máquina de Turing 30 L Left R Right Variantes Tanto a Máquina de Turing formal que já definimos como suas variantes reconhecem as mesmas linguagens 31 Variantes Tanto a Máquina de Turing formal que já definimos como suas variantes reconhecem as mesmas linguagens Semelhante ao que observamos nos AFD e AFND 32 Máquina de Turing com múltiplas fitas 33 Máquina de Turing com múltiplas fitas 34 Máquina de Turing com múltiplas fitas A ideia da Máquina de Turing com múltiplas fitas multifita é aumentar a liberdade de quem está construindo o modelo 35 Máquina de Turing com múltiplas fitas A ideia da Máquina de Turing com múltiplas fitas multifita é aumentar a liberdade de quem está construindo o modelo Por outro lado com mais fitas temos uma maior complexidade para o modelo que poderá ser gerado 36 Máquina de Turing com múltiplas fitas A ideia da Máquina de Turing com múltiplas fitas multifita é aumentar a liberdade de quem está construindo o modelo Por outro lado com mais fitas temos uma maior complexidade para o modelo que poderá ser gerado 𝛅 Q x 𝚪k Q x 𝚪k x L RPk função de transição Modelo com k fitas 37 Máquina de Turing com múltiplas fitas Em uma Máquina de Turing Multifita a string encontrase inicialmente na fita 1 e as demais estão vazias 38 Máquina de Turing com múltiplas fitas Em uma Máquina de Turing Multifita a string encontrase inicialmente na fita 1 e as demais estão vazias A leitura e a escrita em uma Máquina de Turing Multifita ocorre de forma independente em cada fita 39 Máquina de Turing com múltiplas fitas Toda Máquina de Turing Multifita tem uma Máquina de Turing de fita equivalente com uma única fita 40 Máquina de Turing com múltiplas fitas Toda Máquina de Turing Multifita tem uma Máquina de Turing de fita equivalente com uma única fita Uma aplicação das Máquinas de Turing Multifita é a geração de strings nas fitas 2 em diante a partir da string presente na fita 1 41 Máquina de Turing NãoDeterminísticas 42 Máquina de Turing NãoDeterminísticas Assim como os autômatos que podemos ter modelos não determinísticos ao introduzirmos a ideia de múltiplas instâncias de um mesmo autômato as Máquinas de Turing também apresentam a possibilidade de termos múltiplas instâncias simultâneas 43 Máquina de Turing NãoDeterminísticas Assim como os autômatos que podemos ter modelos não determinísticos ao introduzirmos a ideia de múltiplas instâncias de um mesmo autômato as Máquinas de Turing também apresentam a possibilidade de termos múltiplas instâncias simultâneas 𝛅 Q x 𝚪 𝓟Q x 𝚪 x L R 44 Máquina de Turing NãoDeterminísticas Toda Máquina de Turing NãoDeterminística tem uma Máquina de Turing Determinística equivalente 45 Máquina de Turing NãoDeterminísticas Toda Máquina de Turing NãoDeterminística tem uma Máquina de Turing Determinística equivalente Assim como feito com os AFND uma Máquinas de Turing NãoDeterminística aceita uma string quando uma de suas instâncias alcança um estado de aceitação 46