Computabilidade e Linguagens Formais
 Autómatos
finitos
Gabriel David / Cristina Ribeiro
1
Dinheiro electrónico

Definir um protocolo para a utilização de dinheiro electrónico
–
–
Um ficheiro que o cliente tem e envia à loja para pagamento de bens
A “emissão” do ficheiro compete a um banco e é personalizada para o
cliente para reduzir as hipóteses de falsificação e de cópia



Falsificação: técnicas criptográficas
Cópia: intervenção do banco nas transacções e um protocolo de utilização que
garanta que só as operações permitidas são efectuadas – modelar por autómato
Interacção entre os participantes, em cinco eventos
–
–
–
–
–
O cliente paga (enviar o dinheiro/ficheiro para a loja)
O cliente cancela (enviar o dinheiro para o banco que credita a conta do
cliente nesse valor)
A loja entrega os bens ao cliente
A loja redime o dinheiro (envia o ficheiro para o banco e recebe outro no
mesmo valor mas em seu nome)
O banco transfere o dinheiro do cliente para a loja (cria novo ficheiro)
Autómatos finitos-2
Protocolo


Estudo para um só ficheiro; reprodutível para milhões
Assume-se que o cliente não é de confiança
–

O banco é de confiança
–

Pode tentar copiar o dinheiro, pagar várias vezes com o mesmo ou
pagar e cancelar com o mesmo
Deve controlar que a mesma loja, ou duas diferentes, não tentam
redimir o mesmo dinheiro ou que não se redime e cancela
A loja deve ter cuidado em não entregar os bens antes de ter
a certeza de que o dinheiro é válido
Autómatos finitos-3
Modelo separado

Comportamento de cada participante descrito por um
autómato
–
–
–
Estado corresponde a uma situação do participante e memoriza os
eventos ocorridos ou não
As transições entre estados dão-se quando os eventos ocorrem
Eventos externos, independentemente de quem os desencadeia

–
Interessam as sequências de eventos e não quem os pode causar
Num autómato só se representam os eventos que afectam o
participante

Quando o cliente paga à loja o banco não é afectado; só sabe do facto
quando a loja redime o dinheiro
Autómatos finitos-4
Banco
2
cancela
Start



1
redime
3
transfere
4
Estado 1: o banco emitiu o dinheiro, debitando na conta do cliente, e
nada mais aconteceu
Se o cliente cancelar, o banco devolve o dinheiro, creditando o cliente,
e passa para o estado 2, de onde não sairá
Se, em 1, a loja redimir o dinheiro, passa para o estado 3 e, logo que
tenha preparado o dinheiro para a loja, transfere-o e fica em 4 de vez
Autómatos finitos-5
Loja e Cliente
a
Start
paga
b
redime
d
entrega
entrega
Loja

e
transfere
f
entrega
g
Start
Cliente
Enquanto que o banco faz sempre o que deve, a loja pode cometer erros
–
–

c
redime
transfere
cancela
paga
A entrega e as operações financeiras são processos separados que podem
ocorrer por qualquer ordem
Se o dinheiro se vier a revelar inválido, pode acontecer ter já entregue os
bens e não chegar a receber
O cliente não tem restrições, pelo que pode pagar e cancelar várias
vezes, ficando sempre no mesmo estado
–
Compete ao banco garantir que o processo funciona bem
Autómatos finitos-6
Ignorar acções

Faltam várias transições
–
–
–


O evento cancelar não afecta a loja
Mas, pela sua definição formal, um autómato finito, cada vez que
recebe uma entrada X, tem que seguir o arco X, nem que seja para o
mesmo estado, senão morre
Portanto há que acrescentar arcos para todos os eventos mantendo o
estado quando este não é afectado
Isto resolve o problema das entradas maliciosas, por
exemplo um segundo evento paga, no estado e, que também
mataria o autómato
Para simplificar, arcos entre os mesmos estados
representam-se como um único, com várias etiquetas
Autómatos finitos-7
Transições completas
paga, entrega
2
paga, cancela,
paga, cancela,
entrega, redime entrega, redime
cancela
Banco
a
Start
redime
3
paga
b
redime
d
c
redime
paga, cancela
e
transfere
paga, cancela, entrega
redime, transfere
f
entrega
transfere
paga, cancela
4
paga, cancela
entrega
entrega
Loja
transfere
paga, entrega
paga, cancela
paga, cancela
cancela
Start
1
g
Start
Cliente
paga, cancela
Autómatos finitos-8
Interacção


Cliente nunca morre nem muda de estado
Falta perceber quais as combinações de estados que podem
ocorrer entre o banco e a loja – autómato produto
–


Tem um nó por cada par de nós dos dois autómatos separados
Há estados não acessíveis
É possível estudar o comportamento global (validar o
protocolo) e perceber que é possível entregar os bens e não
chegar a receber o dinheiro
–
–
Caso do (2,c)
No caso (3,e) ainda há esperança
Autómatos finitos-9
Autómato produto
a
1
P
b
d
c
P
P
e
P
P
S
P
f
g
P
S
S
Start
R
C
C
C
P
C
P
P
P,C
S
R
C
C
S
P
P
P
P,C
P,C
P,C
S
S
R
T
P
4
C
R S
P,C
C
S
P
P,C
P,C
3
C
S
P
2
R
R
P,C
T
S
P,C
S
P,C
P,C
P,C
Autómatos finitos-10
Autómatos finitos deterministas (DFA)

Determinista
–

Num estado, para cada entrada, há apenas uma transição possível
Um DFA consiste de
–
–
–
Conjunto finito de estados (Q)
Conjunto finito de símbolos de entrada ()
Função de transição de estados e entradas para estados ( p = (q,a) )

um diagrama do DFA é um grafo que representa 
–
Estado inicial (q0  Q)
Conjunto de estados finais ou de aceitação (F  Q)
–
DFA:
–
A = (Q,  , , q0, F)
Autómatos finitos-11
Processar cadeias

A linguagem de um autómato é o conjunto de todas as
cadeias que o DFA aceita
–
–
–
–
Cadeia de entrada: a1a2… an
Estado inicial: q0
Evolução: (qi-1,ai) = qi
Se qn  F então a cadeia está aceite
Autómatos finitos-12
Definir um DFA

Exemplo: reconhecedor de cadeias binárias que contenham a
sequência 01
–
–
–
–
–
{x01y | x e y são cadeias de 0’s e 1’s}
 = {0,1}
Q, tem que memorizar se já viu 01 (q1), se acabou de ver o 0 (q2),
ou se não viu nada de relevante (q0) Q={q0, q1, q2}
Estado inicial: q0
Função de transição de estados



–
–
(q0,1) = q0
(q2,0) = q2
(q1,0) = q1
(q0,0) = q2
(q2,1) = q1
(q1,1) = q1
Estados finais: {q1}
A = (Q,  , , q0, F) = ({q0, q1, q2}, {0,1}, , q0, {q1})
Autómatos finitos-13
Diagramas de transição

Diagrama de transição para um DFA A = (Q,  , , q0, F) é
um grafo
–
–
estado em Q  nó
(q,a) = p onde q, p  Q e a    arco de q para p com etiqueta a

–
–
Vários arcos de q para p juntam-se, fazendo lista de etiquetas
estado inicial  seta com Start
estados em F  círculo duplo no nó
1
Start
q0
0
0
q2
1
q1
0, 1
Autómatos finitos-14
Tabelas de transição

Tabela de transição é representação tabular da função 
–
–
–
–
Estados  linhas
Entradas  colunas
Estado inicial  seta
Estados finais  asterisco
0
1
q0
q2
q0
*q1
q1
q1
q2
q2
q1
Autómatos finitos-15
Extensão da função de transição

Linguagem do DFA
–

Função de transição estendida ^(q,w) = p
–
–
–

Conjunto das sequências de etiquetas para todos os caminhos do nó
de entrada até um dos nós de aceitação
q
w
p
estado
cadeia de entradas
estado a que se chega partindo de q e aplicando w
Definição indutiva em |w|
–
–
Base: ^(q,) = q
Indução: seja w=xa então ^(q,w) = (^(q,x), a)

Se ^(q,x) = p e (p,a) = r, para ir de q até r, vai-se de q até p e um passo
final para r
Autómatos finitos-16
Linguagem de um DFA

Evolução do DFA que lê cadeias com nº par de 0’s e de 1’s
para entrada w = 110101
–
–
–
–
–

Linguagem de um DFA A = (Q,  , , q0, F) é
–

^(q0,) = q0
^(q0,1) = (^(q0, ),1) = (q0,1) = q1
^(q0,11) = (^(q0,1),1) = (q1,1) = q0
…
^(q0,110101) = (^(q0,11010),1) = (q1,1) = q0
L(A) = {w | ^(q0,w)  F}
Se uma linguagem L é L(A) para um DFA A então é uma
linguagem regular
Autómatos finitos-17
Autómatos com transições 

Exemplo: -NFA que aceita números decimais
–
–
–
–
Sinal + ou – optativo
Cadeia de dígitos
Um ponto decimal
Outra cadeia de dígitos (pelo menos uma das cadeias não vazia)
0,…,9
Start
q0
,+,-
q1
0,…,9
.
q2
0,…,9
q3

q5
.
0,…,9
q4
Autómatos finitos-18
Notação formal -NFA

-NFA E = (Q,  , , q0, F)
–
A principal diferença está na função de transição (q,a), para lidar com 

Estado q  Q e entrada a    {}

Exemplo: E = ({q0, q1, q2, q3, q4, q5}, {.,+,-,0,…,9}, , q0, {q5})

0 símbolo da cadeia vazia  não é visível
na cadeia de dígitos
–
–


+,-
.
0,…,9
q0 {q1} {q1}


Representa transições “espontâneas”
Lida-se com ele da mesma forma que com q

{q2} {q1 q4}

1
o não-determinismo, considerando que o
q2



{q3}
autómato pode estar em qualquer dos
estados antes ou depois da transição 
q3 {q5}


{q3}
Para saber todos os estados a que se
“chega” numa transição para um estado q,
calcula-se EClose(q)
–

EClose(q0)= {q0,q1}; EClose(q3)= {q3,q5}
q4


{q3}

*q5




Autómatos finitos-19
Transições estendidas

EClose( q )
Base: o estado q está em EClose(q)
– Indução: se p está em EClose(q) e existe uma transição de p para r com
etiqueta , então r também está em EClose(q)
 Transições estendidas ̂
– Base: ̂ (q,) =EClose(q)
– Indução: w=xa, a   (portanto a ≠ )
 1. seja ̂ (q,x)={p1, p2, …, pk}
–

–
2. 
k
i 1
 ( p i , a )  { r1 ,..., rm }
m
ˆ
EClose ( r j )
 3.  ( q , w )  
j 1
(1) dá os estados a que se chega a partir de q seguindo um caminho
etiquetado com x que pode incluir e terminar numa ou mais transições 
Autómatos finitos-20
Eliminação de transições 

Dado um -NFA E existe sempre um DFA D equivalente
–

Técnica da construção de subconjuntos
–



-NFA E = (QE,  , E, q0, FE)  DFA D = (QD,  , D, qD, FD)
QD é o conjunto dos subconjuntos de QE fechados 
–

E e D aceitam a mesma linguagem
S= EClose(S)
Estado de partida qD = EClose(q0)
FD = {S | S está em QD e S ∩ FE ≠}
Transição D(S,a), para a em  e S em QD
–
–
–
S={p1, p2, …, pk}
k
Calcular  i 1  E ( p i , a )  { r1 ,..., rm }
m
ˆ
Terminar com  D ( S , a )   j 1 EClose ( r j )
Autómatos finitos-21