LFA - linguagens

LFA – P1
UNIP
Professor:___________________________...
Nome do aluno:_______________________________________________________
RA:__________________________

Boa Sorte !!
(1,5)

1

Seja M uma máquina de Turing. Determine a configuração α correspondente a cada situação.
(a) M está no estado s3 e lendo a terceira letra da expressão de fita w = aabca.
(b) M está no estado s2 e lendo a última letra da expressão de fita w = abca.
(c) A entrada é a expressão de fita w = 14B 1 2 .

(1,0)

2

Para cada máquina da Figura 2 com conjunto de entrada A = {a,b} e conjunto de saída Z=[x,y,z } , ache
2 2 2 2 a palavra de saída v se a entrada é a palavra ir = aba b ab a ba.

(1,0)

3

Assinale quantas seqüências de caracteres a seguir são reconhecidas pelo autômato finito abaixo.
As quadro seqüências de caracteres (separadas por vírgulas) são 0, 567, -89.5, -3e3.

(a) 0
(b) 1
(c) 2

(d) 3
(e) 4

(1,0)

4

Ache [E] para as expressões:
(a) E = a11s2Bb111.
(b) E = aas3bb.

(1,5)

5

Seja f a função f(n) = n - 2 s e n > 1 e f(n) = 0 se n = 0 ou 1. Mostre que f é computável.

(1,5)

6

Suponha que α = abs2aa é uma configuração. Ache β tal que α → β se a máquina de Turing M tem a quíntupla q onde:
(a) q = s2abs2N.
(b) q = s2abs3L.
(c) q = s3abs2R.

(1,0)

7

A Máquina de Turing consiste de uma unidade de controle e uma fita. A comunicação entre tais dispositivos se faz mediante uma "cabeça" de leitura/gravação capaz de ler e alterar os símbolos da fita de entrada, conforme o estado em que se encontra a unidade de controle. A cabeça de leitura/gravação pode se mover à direita e à esquerda. Em seu modelo original, a fita se estende indefinidamente à direita, mas é limitada à esquerda. Considere as seguintes afirmações:
I) Se ao modelo original da Máquina de Turing forem acrescentadas duas fitas de entrada, a capacidade de computação do dispositivo obtido é aumentado.
II) Em sua definição formal, a Máquina de Turing