UNIVERSIDADE ESTADUAL DE MARINGÁ – UEM CENTRO DE TECNOLOGIA – CTC DEPARTAMENTO DE INFORMÁTICA – DIN BACHARELADO EM INFORMÁTICA DISCIPLINA: LINGUAGENS FORMAIS E AUTÔMATOS PROFESSOR: YANDRE MALDONADO E GOMES DA COSTA

Lista de Exercícios no 8 – Máquina de Turing

1) Construa Máquinas de Turing determinísticas transdutoras com as seguintes

características:

a) Receba como entrada uma seqüência binária e produza como resultado o valor binário multiplicado por 4;

b) Receba como entrada uma seqüência binária e produza como resultado o valor binário incrementado em uma unidade;

S0 S1 Sf

(0,0,D) (1,1,D)

(β,0,D) (β,0,E) S2

(0,0,E) (1,1,E)

(⟨, ⟨,D)

(0,0,D) (1,1,D)

início soma retorno saída

vai um

estouro

avança

(ββββ,ββββ,E) (0,1,E)

(1,0,E)

(0,0,E) (1,1,E)

(0,1,E)

(⟨⟨⟨⟨,⟨⟨⟨⟨,D)

(⟨⟨⟨⟨,⟨⟨⟨⟨,D)

(1,0,E)

(0,0,D)

(0,1,D)

(ββββ,0,E)

2) Descreva o resultado do processamento da cadeia “111” pela MT construída no item b do exercício número 2.

início

⇓

⟨ 1 1 1 β β ... início

⇓

⟨ 1 1 1 β β ... início

⇓

⟨ 1 1 1 β β ... início

⇓

⟨ 1 1 1 β β ... soma

⇓

⟨ 1 1 1 β β ... vai um

⇓

⟨ 1 1 0 β β ... vai um

⇓

⟨ 1 0 0 β β ... vai um ⇓

⟨ 0 0 0 β β ... estouro

⇓

⟨ 0 0 0 β β ... avança

⇓

⟨ 1 0 0 β β ... avança

⇓

⟨ 1 0 0 β β ... avança

⇓

⟨ 1 0 0 β β ... retorno

⇓

⟨ 1 0 0 0 β ... retorno

⇓

⟨ 1 0 0 0 β ... retorno

⇓

⟨ 1 0 0 0 β ... retorno

⇓

⟨ 1 0 0 0 β ... saída

⇓

⟨ 1 0 0 0 β ... 3) Construa Máquinas de Turing determinísticas reconhecedoras para as seguintes

linguagens:

a) {w ∈ {a, b}* | |w|a=|w|b}; M = (∑∑∑∑, Q, δδδδ, S0, F, V, ββββ, ⟨⟨⟨⟨), onde: ∑∑∑∑ = {a, b} Q = {S0, S1, S2, S3, S4} S0 = estado inicial F = {S4} V = {A, B} ββββ = símbolo branco ⟨⟨⟨⟨ = símbolo de início da fita δδδδ = função programa, conforme tabela abaixo: Tabela de transições: δδδδ ⟨⟨⟨⟨ a b A B ββββ S0 - (S1,A,D) (S3,B,D) (S0,A,D) (S0,B,D) (S4,β,E) S1 - (S1,a,D) (S2,B,E) (S1,A,D) (S1,B,D) - S2 (S0,⟨,D) (S2,a,E) (S2,b,E) (S2,A,E) (S2,B,E) - S3 - (S2,A,E) (S3,b,D) (S3,A,D) (S3,B,D) - S4 - - - - - -

Diagrama de transições:

b) {ww | w ∈ {a, b}*};

S0

S4

S1 S2

S3

(β,β,E) (a,a,D) (A,A,D) (B,B,D)

(a,A,D)

(⟨,⟨,D) (A,A,D)

(B,B,D)

(b,B,E)

(B,B,D) (A,A,D)

(b,b,D)

(B,B,E) (A,A,E)

(b,b,E) (a,a,E)

(a,A,E) (b,B,D)

(X,X,D) (a,A,D)

(A,A,E) (B,B,E) (ββββ,ββββ,E)

(⟨⟨⟨⟨,⟨⟨⟨⟨,D)

(a,A,E) (b,B,E)

(a,A,D) (b,B,D)

S0 S1 S2

Sf

S5

S4

S3

S7

S8

S6

(ββββ,ββββ,E)

(a,a,D) (b,b,D)

(a,a,E) (b,b,E)

(A,A,D) (B,B,D)

(A,A,E) (B,B,E)

(A,a,E) (B,b,E)

(b,B,D)

(a,a,D) (b,b,D) (X,X,D)

(a,a,D) (b,b,D) (X,X,D)

(a,a,E) (b,b,E) (X,X,E)

(A,A,D) (B,B,D)

(B,X,E)

(A,X,E)

c) {anbn | n≥0}; d) {anbncn | n≥0}.

4) Fale sobre a importância da Teoria da Computação para a Ciência da

Computação. Um importante papel da Teoria da Computação na formação de um Cientista da Computação é ajudar a entender o que é computação e todos os elementos

S0 S1 S2

Sf

(ββββ,ββββ,E) (B,B,D)

(a,a,E) (B,B,E)

(⟨⟨⟨⟨,⟨⟨⟨⟨,D)

S3 S4

(B,B,E) (A,A,E)

(ββββ,ββββ,E)

(B,B,D)

(a,A,D)

(A,A,D)

(a,a,D) (B,B,D)

(b,B,E)

S0 S1 S2

Sf

(ββββ,ββββ,E) (B,B,D)

(b,b,D) (C,C,D)

(⟨⟨⟨⟨,⟨⟨⟨⟨,D)

S4 S5

(C,C,E) (B,B,E) (A,A,E)

(ββββ,ββββ,E)

(B,B,D) (C,C,D)

(a,A,D)

(a,a,D) (B,B,D)

(b,B,D)

S3

(a,a,E) (B,B,E) (b,b,E) (C,C,E)

(A,A,D)

(c,C,E)

envolvidos neste contexto - entre eles podemos ressaltar programas, máquinas e os limites computacionais. O estudo de Teoria da Computação justifica-se pela necessidade de se estabelecer que problemas são solucionáveis e que problemas são computáveis. De outra forma podemos dizer que estuda-se os limites da computabilidade, ou seja, quais problemas podem ser resolvidos com um computador. Esta verificação é importante a fim de se evitar por exemplo que sejam despendidos esforços em busca da solução de problemas que não têm solução. A Máquina de Turing, enquanto modelo que define os limites computacionais, é muito importante neste contexto. Assim sendo, algumas das questões muito importantes que o conhecimento contido nesta disciplina ajuda a responder são:

- Existe programa para solucionar um determinado problema? - De que forma um programa pode ser especificado? - Dado um programa qualquer, ele sempre tem parada garantida? - Dois programas A e B são equivalentes entre si? - Duas máquinas X e Y são equivalentes entre si? - Uma determinada solução é a melhor solução para um determinado

problema? - Qual o significado de um determinado programa? - Como construir um programa correto?

Além disso, a Teoria da Computação favorece o desenvolvimento do raciocínio lógico e formal, e traz também conceitos fundamentais para algumas subáreas da computação, como:

- Representação de linguagens: mecanismos de reconhecimento e geração de linguagens. Importante para o desenvolvimento de compiladores e de forma mais geral para o estudo de Linguagens de Programação;

- Processamento de funções: importante para a resolução de problemas e otimização de programas;

- O conceito de não determinismo (não seqüencial) e sua relação com o conceito de concorrência.