3 AUTÓMATOS FINITOS
AUTÓMATOS FINITOS
Sistemas com um número finito de estados:
Elevador
Circuitos booleanos
Jogos de tabuleiro
Computadores
Cérebro humano
Etc.
Como definir uma linguagem com um autómato finito?
Construir um autómato finito que verifique se uma palavra
pertence à linguagem
2
AUTÓMATOS FINITOS DETERMINISTAS
Um autómato finito é um 5-tuplo A=(Q,I, ,q0,F) em que:
Q é um conjunto finito não vazio, cujos elementos se
designam estados;
I é um alfabeto, designado por alfabeto do autómato;
:QxIQ é uma função, designada por função de
transição;
q0 é um estado designado por estado inicial;
F é um subconjunto não vazio de Q, cujos elementos se
designam por estados terminais.
...
Fita de “input”
a
direcção do movimento
b
c
d
...
cabeça de leitura
Dispositivo de controlo
dos estados de A
3
AUTÓMATOS FINITOS DETERMINISTAS
A função  denota um conjunto finito de transições de estado
válidas para o autómato
Os autómatos finitos que aceitam/rejeitam palavras também se
designam por aceitadores finitos.
Exemplo
A=(Q,I, ,q0,F) onde
Q={q0,q1,q2}
(q0,a)=q1
(q0,b)=q2
F={q2}
(q1,a)=q0
(q1,b)=q2
I={a,b}
(q2,a)=q2
(q2,b)=q2
As transições de estado também podem ser descritas através
de uma tabela de transições.
4
AUTÓMATOS FINITOS DETERMINISTAS
Os autómatos finitos também podem ser representados através
de diagramas de transição, ou seja, grafos orientados
etiquetados cujos vértices são representados por:
etiquetado com o identificador do estado inicial,
etiquetado com um identificador de estado terminal
etiquetado com um estado não inicial e não terminal
e cujas arestas são etiquetadas com o símbolo lido do
alfabeto.
Seja A=(Q,I,,q0,F) um autómato finito. Descrição instantânea
de A é um par (q,w) em que q é o estado de A e w é a sequência
de símbolos ainda não lidos.
5
AUTÓMATOS FINITOS DETERMINISTAS
Seja A=(Q,I, ,q0,F) um autómato finito. Próxima descrição
instantânea é a função
P : Q x I*Q x I* tal que
se (q,w1) está definido, então P(q,w) é ((q,w1),’w),
onde ‘w é w sem w[1];
 se não, P(q,w) não está definido.
Seja 0 uma descrição instantânea inicial de um autómato
finito A=(Q,I, ,q0,F). Computação finita de A é uma
sequência de descrições instantâneas 0,1,…,n tal que,
Para todo 0in, P(i) está definido;
Para todo 1in, i é P (i-1) e
P(n) não está definido.
6
AUTÓMATOS FINITOS DETERMINISTAS
As descrições instantâneas em Fx{} designam-se descrições instantâneas
terminais.
As descrições instantâneas em {q0}xI* são descrições instantâneas iniciais.
Seja 0 uma descrição instantânea inicial de um autómato finito
A=(Q,I,,q0,F). Computação infinita de A é uma sucessão de descrições
instantâneas 0,1,… tal que,
a) Para todo 0in, P(i) está definido e
b) Para todo i>0, i é P(i-1).
Para representar a transição de uma descrição instantânea  para P()
escrevemos
  P().
* n para indicar que existe uma sucessão de descrições
Escreve-se 1 
instantâneas 1,2,…, n tal que,
a) Para todo 1in, P(i) está definido e
b) Para todo i > 1, i é P(i-1).
7
AUTÓMATOS FINITOS DETERMINISTAS
Sejam A=(Q,I, ,q0,F) um autómato finito e w uma palavra em I*. w diz-se
classificada por A se e só se a computação iniciada na descrição instantânea (q0,w)
for finita.
Sejam A=(Q,I, ,q0,F) um autómato finito e w uma palavra em I*. Se a descrição
instantânea terminal da computação de w for (q,), com qF, então diz-se que w é
aceite por A, se não, diz-se que w é rejeitada por A.
Uma linguagem sobre um alfabeto diz-se aceite por um autómato finito se coincide
com o conjunto de palavras aceites pelo autómato finito.
A linguagem aceite pelo autómato finito, A=(Q, I, , q0,F), é definida por
L(A):={wI*: (q0,w)
*

(q,) para algum qF}
8
AUTÓMATOS FINITOS DETERMINISTAS
Uma linguagem L sobre um alfabeto diz-se reconhecida por um
autómato finito se L coincide com o conjunto das palavras aceites pelo
autómato finito e Lc coincide com o conjunto das palavras rejeitadas
pelo autómato finito.
Obs.: Lc=I*-L onde I é o alfabeto da linguagem.
Execícios
Construa autómatos finitos que aceitem as seguintes linguagens:
1.L(a(a+b)*);
2.L((a+b)*abb);
3.L(b(a+b)*aa).
9