Informática Teórica
Engenharia da Computação
Teoria é importante para a prática

Ela provê ferramentas conceituais que os
praticantes usam em engenharia da computação.

Projetando uma nova linguagem de programação
para uma aplicacão especializada?
O que você aprender sobre gramáticas neste
curso irá bem a calhar.

Teoria é importante para a prática

Lidando com busca por cadeias e casamento de
padrões?

Lembre-se de autômatos finitos e expressões
regulares.
Teoria é importante para a prática

Lidando com busca por cadeias e casamento de
padrões?

Lembre-se de autômatos finitos e expressões
regulares.
Teoria é importante para a prática

Confrontado com um problema que parece
requerer mais tempo de computador do que você
pode suportar?

Pense no que você aprendeu sobre NP completude.
Teoria é importante para a prática

Os melhores projetos e aplicações de
computadores são concebidos com elegância em
mente.

Um curso teórico pode elevar seu sentido estético
e ajudá-lo a construir sistemas mais bonitos.
Teoria é importante para a prática




Finalmente, teoria é bom para você porque estudála expande sua mente.
Conhecimento técnico específico, embora útil
hoje, fica desatualizado em apenas uns poucos
anos.
Por outro lado as habilidades de pensar, exprimirse claramente e precisamente, para resolver
problemas, e saber quando você não resolveu um
problema.
Essas habilidades têm valor duradouro. Estudar
teoria treina você nessas áreas.
Teoria dos Autômatos



Lida com as definições e propriedades de
modelos matemáticos de computação.
Um modelo, chamado autômato finito, é usado em
processamento de texto, compiladores, e projeto
de hardware.
Um outro modelo, chamado gramática livre-docontexto, é usado em linguagens de programação
e inteligência artificial.
Cadeias e Linguagens

Alfabeto : conjunto de símbolos.

Cadeias sobre um alfabeto.

Tamanho de uma cadeia w: |w|.

Cadeia de tamanho vazio: 

Reverso de w: wR.

Concatenação.

Concatenação de x com si própria: xK.

Linguagem: é um conjunto de cadeias.
Autômatos Finitos

É um dos modelos computacionais que
estudaremos.

Porém com uma quantidade extremamente
limitada de memória.
O que um computador pode fazer com uma
memória tão pequena?
Na verdade, interagimos com tais computadores o
tempo todo, pois eles residem no coração de
vários dispositivos eletromecânicos.


Autômatos Finitos

O controlador para uma porta automática é um
exemplo de tal dispositivo.
 As lavadoras de louça/roupa, termômetros
eletrônicos, relógios digitais, calculadoras e
máquinas de venda automática....
 Os autômatos também são chamados de máquinas
de estados finitos.
Autômatos Finitos: exemplo
Controlador para uma porta automática
Sinal de entrada
Estado
Nenhum
Frente
Atrás
Ambos
Fechado
Fechado
Aberto
Aberto
Fechado
Aberto
Fechado
Aberto
Aberto
Aberto
Esse controlador é um computador com apenas 1 bit de memória,
capaz de registrar em quais dos dois estados o controlador está.
Autômatos Finitos

Ao começar a descrever a teoria matemática de
autômatos finitos, fazemos isso no nível abstrato,
sem referˆência a qualquer aplicação específica.

A seguir vamos ver alguns exemplos usando um
diagrama de estados e identificar os conceitos de:
estado inicial, estado de aceitação ou final,
transição.
Autômatos Finitos

Uma máquina M1 que recebe cadeias de bits como
entrada e aceita somente aquelas que começam
com um ou mais zeros seguidos de um ou mais 1’s
apenas.
Autômatos Finitos

O autômato recebe os símbolos da cadeia de entrada
um por um da esquerda para a direita.
 Após ler cada símbolo, M1 move de um estado para
outro ao longo da transição que tem aquele símbolo
como seu rótulo.
 Quando ele lê o último símbolo, M1 produz sua saída.
 A saída é aceite se M1 está agora no estado de
aceitação e rejeite se ele não está.
Autômatos Finitos

Um AF que recebe cadeias de bits e aceita aquelas
que possuem 10 como subcadeia
Autômatos Finitos
0
q0
1
1
q1
0
q3
0,1
Autômatos Finitos
M2
q0
0
1
0
1
L(M2)={w | w termina em 1}
q1
Autômatos Finitos
M3
1
1
0
q0
q1
0
L(M3)={w | w é a cadeia vazia  ou termina em 0}
Autômatos Finitos
a
M4
q0
b
a
q2
q1
b
b
a
a
b
q3
q4
b
a
L(M4)={w | w começa e termina no mesmo símbolo}
Autômatos Finitos
a
q0
b
q1
a
b
q2
a
q3
b
a,b
Os estados q1 e q2 servem para “memorizar’’ o símbolo anterior.
Esse AF aceita as cadeias sobre o alfabeto {a,b} que possuem aa
ou bb como subcadeias.
Autômatos Finitos
q0
0
1
q1
1
0
1,0
q3
Esse AF aceita qualquer cadeia binárias que termina com o símbolo 1 ou
que termina com um número par de 0s seguindo o último 1.