Linguagens Formais e Autômatos

Lista de Exercícios No. 05

Máquina de Turing

1) Qual a importância da Máquina de Turing para a Ciência da Computação?

2) Para cada uma das linguagens abaixo, desenvolva uma Máquina de Turing que a aceita e que, sempre

para, para qualquer entrada:

a) b) {ɛ}

c) {ɛ, a, b}

d) {a, b}*

e) {anb

nc

n | n 0}

f) {w | w é palavra de {x, y, (, )}* com parênteses balanceados}

3) Desenvolva um programa em computador que simule qualquer Máquina de Turing. As entradas devem ser

os componentes da máquina e a palavra a ser processada. Como saídas, o simulador deve apresentar o

estado final da máquina simulada, o conteúdo da fita e o número de movimentos da cabeça da fita.

4) Sobre a Hipótese de Church:

a) Por que não é demonstrável?

b) Qual o seu significado?

c) Qual a sua importância?