Linguagens Formais e Aut matos Aula 5 AFND Com Transi es Vazias 13.09.2016

Prévia do material em texto

Professor
Me. Paulo David
pd.mnpa@gmail.com
Faculdade Maurício de Nassau
Curso: Sistemas de Informação 
Disciplina: Linguagens Formais e Autômatos
Professor: Me. Paulo Roberto Sousa David
Autômatos Finitos Com 
Movimentos Vazios ()
• Os movimentos vazios generalizam os
movimentos não determinísticos.
• Um movimento vazio é uma transição sem a
leitura de símbolo da fita (símbolo de
entrada).
• Pode ser interpretado como um não
determinismo interno ao autômato,
constituindo uma transição encapsulada.
• Essa transição (encapsulada) executa uma
eventual mudança de estado, nada mais por ser
observado um movimento vazio.
• Uma das vantagens dos autômatos finitos com
movimentos vazios no estudo das linguagens
formais é o fato de facilitarem algumas
construções e demonstrações relacionadas
com os autômatos.
• Movimento vazio (transição ) corresponde a:
 uma transição sem leitura de símbolo.
 transição não obrigatória.
• A computação de um Autômato Finito com
Movimentos Vazios é análoga à de um AFND.
• Assim, um AFND, ao processar uma entrada
vazia, assume simultaneamente os estados
destino e origem.
• Portanto, a origem de um movimento vazio
sempre é um caminho alternativo (daí o não
determinismo).
Definição 18: Um Autômato Finito Não
Determinístico e com Movimentos Vazios
(AFND) ou, simplesmente, Autômato Finito
com Movimentos Vazios é uma 5-upla M =
(K,Σ,,s,F) onde:
• K (ou Q), Σ, s e F são definidos como no AFD.
•  (ou ) é uma relação (denominada relação de
transição) sobre K×(Σ∪ {}).
• Assim, para um estado p e um símbolo a:
δ(p, ) = {q’, q”, q’’’,...}.
é um movimento vazio ou uma transição vazia do 
autômato.
• A parada do processamento de um Autômato
Finito com Movimentos Vazios (AFND) é
análoga à do AFND, assim como as definições
de linguagem aceita e linguagem rejeitada.
• A representação da função programa como um
diagrama é análoga à do AFND.
• Supondo que δ(p, ) = {q1}, δ(p, a1) = {q2}...
δ(p, an) = {qn}.
p
q2
a1
Estado
Anterior
Símbolo
Lido
Conjunto
de Novos
Estados
q1 qn
 an
...
Exemplo 1: Seja o AFNDM1 = (K, Σ, ∆, s, F) com
transição vazia a seguir:
qfq0

b
• q0 tem uma transição com a.
• q0 tem transição com .
a
Exemplo 1: Seja o AFNDM1 = (K, Σ, ∆, s, F) com
transição vazia e ∆ dada pela tabela:
 a b
q0
qf
q0 

qf
 qf 
Exemplo 2: Seja o AFND M2 = (K, Σ, ∆, s, F)
com:
• K = {q0, q1, q2}
• Σ = {a, b}
• s = q0
• F = {q2}
• ∆ dada pela tabela:
Exemplo 2: Seja o AFNDM2 = (K, Σ, ∆, s, F) com
transição vazia e ∆ dada pela tabela:
 a b
q0
q1
(q0,q1) q0
q2 ---

---
q2
q2 ------ ---
Exemplo 3: Autômato que reconhece uma adição
de um inteiro positivo ou negativo com um valor
decimal positivo com uma casa decimal.
q0
+
–

q1 q2 q3 q4 q6
q5
1,2,
...9
1,2,
...9
+
1,2,
...9
1,2,
...9

 1,2,
...9
Exemplo: Reconhece a entrada -12 + 2.4
q0
+
–

q1 q2 q3 q4 q6
q5
1,2,
...9
1,2,
...9
+
1,2,
...9
1,2,
...9

 1,2,
...9
–
q0 q1 q2
1
q2
2
q5
q3
+
Fq4
2
q6

 4
Professor
Me. Paulo David
pd.mnpa@gmail.com
Faculdade Maurício de Nassau
Curso: Sistemas de Informação 
Disciplina: Linguagens Formais e Autômatos
Professor: Me. Paulo Roberto Sousa David
Autômatos Finitos Com 
Movimentos Vazios ()