Exerc-TM-L1

Prévia do material em texto

1 Exerćıcios de Máquina de Turing
1.1 Exerćıcio 1: Máquina de Turing que reconhece a Lin-
guagem do Duplo Balanceamento
Considere a linguagem:
DB = {(n)n|n ≥ 0}
Intuitivamente, uma Máquina de Turing que aceita esta linguagem pode ser
definida da seguinte maneira: no estado inicial, a cabeça lê o śımbolo “(”, o qual
pode ser marcado com “x”. A cabeça da fita é então movimentada para à direita,
procurando o “)” correspondente, o qual quando encontrado deve ser marcado
como “y”. Este ciclo é repetido sucessivamente até que seja identificado para
cada “(” o seu correspondente “)”. Adicionalmente, a máquina deve garantir
que qualquer outra palavra que não esteja na forma (n)n seja rejeitada.
Projete uma descrição de baixo ńıvel de um MT que reconhece DB. Simule
a sua solução no JFLAP (simulador de MT).
1.2 Exerćıcio 2: Máquina de Turing como processadora
de funções
Uma abordagem da máquina de Turing é como processadora de funções, i.e.,
funções que mapeiam palavras de um alfabeto Σ entre si.
A idéia intuitiva para a definição desta máquina é que a entrada pode ser
vista como uma palavra do tipo: w1#w2. Inicialmente, a máquina posiciona a
cabeça no último śımbolo da palavra de entrada. Após move a cabeça para a
esquerda até encontrar o śımbolo #, quando pára. Enquanto move a cabeça,
ao ler um śımbolo, grava sobre este o śımbolo lido anteriormente. Um ponto
interessante é a memorização do śımbolo anterior.
Um exemplo é a máquina de Turing para a função concatenação:
conc :: ({a, b}∗)n → {a, b}∗
tal que associa ao par (w1, w2) a palavra w1w2. Projete a MT que computa tal
função. Considere que a entrada é uma palavra w1#w2. Assim, a sáıda deve
ser w1w2. Simule a sua solução no JFLAP (simulador de MT).