Exercicios

1) Transforme em automato finito:  (b*|a)*

2) Transforme em expressao regular:
estados: 1, 2
inicial: 1
finais:  2
transicoes: 1,a,2; 2,a,2; 2,1,2;

3) De um exemplo de linguagem que nao seja regular.
Justifique.

4) Construa o automato finito usado pelo algoritmo
KMP para buscar o pafrao TGTGTGA.

5) Construa uma maquina de Turing que reverte o
conteudo de sua fita.  Exemplo:  ABB  vira  BBA .
O inicio e o fim da fita vem marcados com # e %,
respectivamente.  Suponha que so' haja caracteres
A e B fora os marcadores de inicio e fim.

6) Seja  M_i  a i-esima maquina de Turing, em ordem
alfabetica.  Seja  e_i  a i-esima entrada para maquinas
de Turing.  Voce acha que  M_i  rodando em  e_i  para
para todo i?  Justifique.

7) Proponha um algoritmo para reconhecer 2-SAT, o
conjunto das formulas booleanas que tem no maximo
dois termos por fator.  
Exemplo: (x1 V x2')(x3' V x2)(x1' V x3).
Obs: xi' significa "not xi"

8) Transforme o seguinte automato nao deterministico
em automato deterministico:
estados: 1,2,3,4
inicial: 1
finais: 4
transicoes: 1,b,1; 1,b,2; 2,b,3; 3,a,4; 

9) O que diz o teorema de Cook e qual e' sua importancia?

10) Defina as classes P, NP, P-espaco e NP-espaco e diga
qual e' a relacao entre elas.