Baixe o app para aproveitar ainda mais
Prévia do material em texto
DIAGRAMAS DE TRANSIÇÃO PARA MÁQUINAS DE TURING Marcelo Guerra INTRODUÇÃO É possível representar as transições de uma MT através de diagramas. Um diagrama de transição consiste em: Um conjunto de nós correspondendo aos estados da MT. Um arco do estado q para o estado p é rotulado por um ou mais itens da forma X/YD. X e Y são símbolos da fita. D é o sentido do movimento da cabeça da fita. INTRODUÇÃO Assim, para δ(q, X) = (p, Y, D) Temos um arco rotulado X/Y D de q para p. Nos diagramas, o sentido é indicado por ← “esquerda” ou → “direita”. O estado inicial e os estados finais são representados da maneira usual. O símbolo branco da fita é representado por B. EXEMPLO q0 q1 q2 Y / Y → 0/0 → q4 q3 Y / Y → B / B → 0 / X → Y / Y ← 0 / 0 ← Y / Y → X / X → 1 / Y ← Estado 0 1 X Y B q0 (q1,X,R) (q3,Y,R) q1 (q1,0,R) (q2,Y,L) (q1,Y,R) q2 (q2,0,L) (q0,X,R) (q2,Y,L) q3 (q3,Y,R) (q4,B,R) q4 MÁQUINAS DE TURING COMO TRADUTORES (COMPUTADORES) As máquinas de Turing não são somente interessantes como reconhecedores. Elas nos fornecem modelos abstratos de computadores digitais. Uma vez que o principal objetivo de um computador é transformar entradas em saídas, ele atua como um tradutor. MÁQUINAS DE TURING COMO TRADUTORES (COMPUTADORES) A entrada para uma computação é a cadeia disposta na fita no início da computação. Na conclusão da computação, a saída será a cadeia que se encontrar na fita. Se a máquina pára num estado não final ou fica em laço infinito para uma entrada, dizemos que a MT não está definida para essa entrada. MÁQUINAS DE TURING COMO TRADUTORES (COMPUTADORES) Para computar funções numéricas, há a necessidade de codificação dos números naturais na fita da máquina. Uma possibilidade é codificá-los na notação unária, na qual qualquer inteiro positivo é representado por: Ex: 1 é 1, 2 é 11, 3 é 111, ... 1x EXEMPLO Dados dois inteiros positivos x e y, projetar uma máquina de Turing que compute x + y. Inicialmente, x e y são dispostos na fita e sua soma deve aparecer no final da computação. α(x) e α(y) estão na fita em notação unária, separados por um 0. O cabeçote aponta para o símbolo mais à esquerda de α(x). q0α(x)0α(y) ⊦ qf α(x+y)0 EXEMPLO Tudo o que precisamos fazer é mover o separador 0 para a direita, até o final de α(y). Deste modo, a adição nada mais é do que concatenar as duas cadeias. Ex: 2 + 3 => 11 + 111 => 11111 EXEMPLO M = {Q, Σ, Γ, δ, q0, B, F}, Com: Q = {q0, q1, q2, q3, q4} Σ = {0 ,1} Γ = {0,1,B} F = {q4} 0 1 B q0 (q1, 1, D) (q0, 1, D) q1 (q1, 1, D) (q2, B, E) q2 (q3, 0, E) q3 (q3, 1, E) (q4, B, D) q4 EXEMPLO Somar 111 com 11: q0111011 ⊦ 1q011011 ⊦ 11q01011 ⊦ 111q0011 ⊦ 1111q111 ⊦ 11111q11 ⊦ 111111q1B ⊦ 11111q21 ⊦ 1111q310 ⊦ 111q3110 ⊦ 11q31110 ⊦ 1q311110 ⊦ Bq3111110 ⊦ Bq3B111110 ⊦ Bq4111110 A LINGUAGEM DE UMA MT Uma MT aceita uma linguagem da seguinte forma: Uma string de entrada é colocada na fita. A cabeça aponta para o símbolo mais à esquerda. Se a MT entrar em um estado de aceitação, a entrada será aceita. Caso contrário, será rejeitada. PARADA PARA MT’S Uma segunda noção de “aceitação” para MT’s é a aceitação por parada. Dizemos que uma MT pára se ela entra em um estado q, varrendo um símbolo da fita X e não existe mais nenhum movimento nessa situação. Ou seja, δ(q, X) está indefinido Algumas máquinas não são projetadas para reconhecer uma linguagem, e sim, calcular funções. Nesse caso, não há a necessidade de um estado de aceitação PARADA PARA MT’S Sempre podemos supor que uma MT irá parar se ela aceitar a string de entrada. Ou seja, sem alterar a linguagem podemos tornar δ(q, X) indefinido sempre que q for um estado de aceitação. Em geral dizemos que: Uma MT sempre pára quando se encontra em um estado de aceitação. A LINGUAGEM DE UMA MT Seja M = (Q, Σ, Γ, δ, q0, B, F) uma MT. L(M) é o conjunto de strings w em Σ* tais que q0w ⊦ * αpβ para algum estado p em F e quaisquer strings de fita α e β. O conjunto de linguagens que podem ser aceitas por MT’s é chamado de Linguagens Recursivamente Enumeráveis. Segundo a Hipótese de Church, a MT é o mais geral dispositivo de computação. Então, as linguagens recursivamente enumeráveis representam todas as linguagens que podem ser reconhecidas mecanicamente e em tempo finito. A LINGUAGEM DE UMA MT Linguagens Recursivamente Enumeráveis Formalismo: Gramática Irrestrita. Para algumas dessas linguagens, é impossível determinar mecanicamente se uma palavra não pertence a L. Existe pelo menos um w não pertencente a L, que ao ser processada por MT, a máquina entra em loop infinito. A classe das linguagens para as quais existe pelo menos uma MT que pára para qualquer entrada, aceitando-a ou rejeitando-a chama-se Linguagens Recursivas. A LINGUAGEM DE UMA MT As linguagens sensíveis ao contexto são aquelas que podem ser aceitas por uma máquina de Turing com fita limitada. Formalismo: Gramática Sensível ao contexto. A classe das linguagens sensíveis ao contexto está contida na classe das linguagens recursivas. HIERARQUIA DAS LINGUAGENS Linguagens Recursivamente Enumeráveis Linguagens Recursivas Linguagens Sensíveis ao contexto Linguagens Livres de Contexto Linguagens Regulares EXERCÍCIO A MT permite calcular qual função matemática? Resp: f(n)=n+1 EXERCÍCIO Dada a MT abaixo, verifique se as sentenças a seguir são aceitas ou não: aabbcc abbacc Resposta: sim e não EXERCÍCIO Qual linguagem é representada pela MT abaixo? anbncn para n>=0
Compartilhar