Python

Aut´matos finitos n˜o determin´ o a ısticos (AFND)
[HMU00](Cap 2.3)
Computa¸˜es n˜o determin´ co a ısticas: o estado seguinte n˜o ´ univocamente ae determinado pelo estado actual.Num aut´mato finito (n˜o-determ´ o a ınistico): • dado um estado s e um s´ ımbolo a existe um conjunto de estados poss´ ıveis seguintes, do qual se pode escolher um novo estado
• uma palavra ´ aceite, se come¸ando no estado inicial existe um conjunto e c de escolhas (caminho) tal que quando acabar de a ler est´ num estado a final.
• uma palavra ´ rejeitada se n˜o existe nenhum caminho que leve dum e a estado inicial a um estado final.
Departamento de Ciˆncia de Computadores da FCUP — MC — Aula 5 e 1

Escolher ou adivinhar e verificar
L = {x ∈ {0, 1} | o quinto s´ ımbolo a contar da direita ´ 1} e 0,1

GF

@A
/

ED

pqrs wvut s0

1

pqrs
/ wvut

s1

0, 1

pqrs
/ wvut

s2

0, 1

wvut
/ pqrs

s3

0,1

wvut
/ pqrs

s4

0, 1

Se x ∈ L existe uma escolha que leva ` aceita¸˜o; se x ∈ L nenhuma a ca
/
escolha leva ` aceita¸˜o. a ca
Facto: existe um aut´mato finito determin´ o ıstico que aceita L, mas tem pelo menos 25 = 32 estados , pois tem de “recordar” os ultimos 5 s´
´
ımbolos lidos! Departamento de Ciˆncia de Computadores da FCUP — MC — Aula 5 e 2

wvut hijk onml
/ pqrs

s5

AFD e AFND
Um aut´mato finito determin´ o ıstico ´ um caso particular dum aut´mato e o finito n˜o determin´ a ıstico.
Mas..
As linguagens aceites por aut´matos finitos n˜o determin´ o a ısticos s˜o precia samente as mesmas das aceites por aut´matos finitos determin´ o ısticos
Isto ´ e Para cada aut´mato finito n˜o determin´ o a ıstico, existe um aut´mato finito o determin´ ıstico que aceita a mesma linguagem.

Departamento de Ciˆncia de Computadores da FCUP — MC — Aula 5 e 3

Constru¸˜o por subconjuntos (informal) ca Ideia: associar um estado do AFD a cada conjunto de estados em que o