Ciencias da computacao

FACULDADE BAURU

Ciência da Computação
Linguagens Formais e Autômatos
Profª. Adriana Andrade [e-mail] Aula 6 – Autômatos Finitos Determinístico

Aula 6:
Autômatos Finitos
Determinístico

Linguagens Regulares
Autômato Finito
• Formalismo operacional/reconhecedor – pode ser:
– Determinístico
• Dependendo do estado corrente e do símbolo lido
• Pode assumir um único estado
– Não determinístico
• Dependendo do estado corrente e do símbolo lido
• Pode assumir um conjunto de estados alternativos

– Com movimentos vazios
• Dependendo do estado corrente e sem ler qualquer símbolo pode assumir um conjunto de estados (portando é não determinístico)
• Os Três tipos de autômatos: equivalentes
– Em termos de poder computacional

Autômatos Finitos NÃO
Determinísticos (AFN)
Um Autômato Finito Não Determinístico, abreviado por AFN, e uma 5-upla ordenada:
M = { Σ, Q, d, q0, F}
Onde:
a) Σ e um alfabeto de símbolos de entrada, ou simplesmente, alfabeto de entrada;
b) Q e o conjunto de estados possíveis do autômato o qual e finito;
c) d e uma função programa ou função de transição ou simplesmente programa: d : Q x Σ → 2Q a qual e uma função parcial. Supondo que a função programa e definida para um estado p e um símbolo a, resultando no conjunto de estados {q1,q2,q3,...,qn}, então: d(p,a)={q1,q2,q3,...,qn} e uma transição do autômato;
d) q0 e um elemento distinguido de Q, denominado estado inicial;

e) F e um subconjunto de Q, denominado conjunto de estados finais.

Autômatos Finitos
Determinísticos (AFD)
M = (Σ, Q, δ, q0, F)
Σ = alfabeto de entrada
{a, b}
Q = conjunto de estados
{q0, q1, q2, qf} δ = função de transição

δ:Q×Σ→Q

{δ (q0, a) = q1, δ (q0, b) = q2 , δ (q1, a) = qf, δ (q1, b) = q2, δ (q2, a) = q1, δ (q2, b) = qf, δ (qf, a) = qf, δ (qf, b) = qf} q0 = estado inicial q0 ϵ Q

F = conjunto de estados finais

Autômatos Finitos
Determinísticos
A função de transição
(ou programa, ou ainda
função