Uma palavra sobre não determinismo
Autômato finito não determinístico
Exemplo
Função programa estendida (para AFNs)
Considerações finais
Teoria de Linguagem
Autômatos Finitos Não Determinísticos
Vinicius H. S. Durelli
B durelli@[Link]
1 / 23
Uma palavra sobre não determinismo
Autômato finito não determinístico
Exemplo
Função programa estendida (para AFNs)
Considerações finais
Organização
1 Uma palavra sobre não determinismo
2 Autômato finito não determinístico
3 Exemplo
Definição formal
4 Função programa estendida (para AFNs)
5 Considerações finais
2 / 23
Uma palavra sobre não determinismo
Autômato finito não determinístico
Exemplo
Função programa estendida (para AFNs)
Considerações finais
Uma palavra sobre não determinismo. . .
O não determinismo é uma importante generalização dos modelos
de máquinas (Menezes 2011), sendo de fundamental importância no
estudo das linguagens formais.
ß A facilidade de não determinismo para autômatos pode ser descrita
como:
Dado o estado corrente e o símbolo lido da entrada, determina-
se aleatoriamente um estado de um conjunto de estados alter-
nativos.
3 / 23
Uma palavra sobre não determinismo
Autômato finito não determinístico
Exemplo
Função programa estendida (para AFNs)
Considerações finais
1 Uma palavra sobre não determinismo
2 Autômato finito não determinístico
3 Exemplo
Definição formal
4 Função programa estendida (para AFNs)
5 Considerações finais
4 / 23
Diferença. . .
Essencialmente, a principal diferença
entre um AFD e um autômato finito q
não determinístico (AFN) é que o pro-
cessamento de uma entrada em um a a a
AFN pode resultar em um conjunto ...
de novos estados (Menezes 2011). p1 p2 pn
Em um AFD cada par (estado, símbolo) representa uma
transição para um único estado.
A cada transição não determinista, novos caminhos
alternativos são possíveis, definindo-se assim uma árvore
de opções.
Uma palavra sobre não determinismo
Autômato finito não determinístico
Exemplo Definição formal
Função programa estendida (para AFNs)
Considerações finais
1 Uma palavra sobre não determinismo
2 Autômato finito não determinístico
3 Exemplo
Definição formal
4 Função programa estendida (para AFNs)
5 Considerações finais
6 / 23
Uma palavra sobre não determinismo
Autômato finito não determinístico
Exemplo Definição formal
Função programa estendida (para AFNs)
Considerações finais
Exemplo (1)
Considere o AFN a seguir:
0, 1
início
q0 0 q1 1 qf
7 / 23
Uma palavra sobre não determinismo
Autômato finito não determinístico
Exemplo Definição formal
Função programa estendida (para AFNs)
Considerações finais
Exemplo (1)
Considere o AFN a seguir:
0, 1
início
q0 0 q1 1 qf
Qual a linguagem aceita pelo AFN?
7 / 23
Uma palavra sobre não determinismo
Autômato finito não determinístico
Exemplo Definição formal
Função programa estendida (para AFNs)
Considerações finais
Exemplo (1)
Considere o AFN a seguir:
0, 1
início
q0 0 q1 1 qf
Qual a linguagem aceita pelo AFN?
Le = {w | w possui 01 como sufixo}
7 / 23
Uma palavra sobre não determinismo
Autômato finito não determinístico
Exemplo Definição formal
Função programa estendida (para AFNs)
Considerações finais
Exemplo (2)
0, 1
início
q0 0 q1 1 qf
Nota-se que o AFN permanece no estado q0 (entre
outros estados), enquanto ele não “adivinhou” que o
sufixo 01 começou.
No estado q0 , para qualquer entrada, o autômato
sempre assume o estado q0 novamente (e o estado
q1 se a entrada for 0).
Quando a entrada é 0, o AFN assume tanto os
estados q0 e q1 .
8 / 23
Exemplo (3): AFN durante o processamento da palavra
00101
Árvore de opções:
q0
[0] [0]
q0 q1
0, 1
[0] [0]
q0 q1 início
q0 0 q1 1 qf
[1] [1]
q0 qf Um AFN aceita uma palavra
[0] [0] se for possível, a partir de
q0 q1 uma sequência de escolhas
de estados, partir do estado
[1] [1] inicial e chegar no estado final.
q0 qf
Definição formal
Excetuando-se δ, os componentes Σ, Q, q0 , e F são como na definição
do AFD.
Definição → Autômato Finito Não Determinístico
Um AFN M é uma quíntupla: M = (Σ, Q, δ, q0 , F ) onde:
Σ representa o alfabeto de símbolos de entrada;
Q é o conjunto finito de estados do autômato;
δ função de transição (δ : Q × Σ → 2Q ) – a qual é uma função
total;
Assim, para um estado p e um símbolo a:
δ(p, a) = {q1 , q2 , . . . , qn }
é uma transição do AFN.
q0 ∈ Q estado inicial;
F ⊂ Q representa o conjunto de estados finais.
Definição formal
Excetuando-se δ, os componentes Σ, Q, q0 , e F são como na definição
do AFD.
Definição → Autômato Finito Não Determinístico
Um AFN M é uma quíntupla: M = (Σ, Q, δ, q0 , F ) onde:
Σ representa o alfabeto de símbolos de entrada;
Q é o conjunto finito de estados do autômato;
δ função de transição (δ : Q × Σ → 2Q ) – a qual é uma função
total;
Assim, para um estado p e um símbolo a:
δ(p, a) = {q1 , q2 , . . . , qn }
é uma transição do AFN.
q0 ∈ Q estado inicial;
F ⊂ Q representa o conjunto de estados finais.
Uma palavra sobre não determinismo
Autômato finito não determinístico
Exemplo
Função programa estendida (para AFNs)
Considerações finais
1 Uma palavra sobre não determinismo
2 Autômato finito não determinístico
3 Exemplo
Definição formal
4 Função programa estendida (para AFNs)
5 Considerações finais
11 / 23
Função programa estendida (1). . .
Para definir formalmente o comportamento de um AFN, é necessário
estender a definição da função programa usando como argumento
um conjunto finito de estados e uma palavra.
Definição → Função Programa Estendida (para AFNs)
Seja M = (Σ, Q, δ, q0 , F ) um AFN, a função programa estendida
de M pode ser denotada por:
δ ∗ = 2Q × Σ∗ → 2Q
sendo a função programa δ : Q × Σ → 2Q estendida para palavras e
indutivamente definida como segue:
δ ∗ (P, ε) = P
δ ∗ (P, aw ) = δ ∗ (
[
δ(q, a), w )
q∈P
q
Função programa estendida (2). . .
A função programa estendida consiste na sucessiva aplicação da
função programa a cada símbolo da palavra, a partir de conjunto
de estados.
δ ∗ ({q1 , q2 , . . . , qn }, a) = δ(q1 , a) ∪ δ(q2 , a) ∪ . . . ∪ δ(qn , a)
Condições de parada
Aceita a entrada w : após processar o último símbolo
da fita, existe pelo menos um estado final entre os
estados alternativos atingidos.
Rejeita a entrada w . Duas possibilidades:
após processar o último símbolo da fita, todos
estados atingidos são não finais; ou
ao longo do processamento de w , o conjunto de
estados alternativos é vazio. O autômato para
por indefinição.
Uma palavra sobre não determinismo
Autômato finito não determinístico
Exemplo
Função programa estendida (para AFNs)
Considerações finais
Exercícios (1)
Considerando o alfabeto Σ = {1, 0}:
Exercício À: Crie um AFD que aceita a linguagem descrita a seguir.
Le1 = {w : w possui 1 na terceira posição do fim para o começo
da palavra}a
a
e.g., 00100 pertence à Le1 , 0011 não.
Exercício Á: Crie um AFN que aceita Le1 .
14 / 23
Uma palavra sobre não determinismo
Autômato finito não determinístico
Exemplo
Função programa estendida (para AFNs)
Considerações finais
Linguagem aceita
Seja M = {Σ, Q, δ, q0 , F } um AFN, a linguagem aceita por M é
denotada:
ACEITA(M) ou L(M)
é o conjunto de todas as palavras pertencentes a Σ∗ aceitas por M
a partir de {q0 }, ou seja:
L(M) = {w | δ ∗ ({q0 }, w ) ∩ F 6= ∅}
15 / 23
Uma palavra sobre não determinismo
Autômato finito não determinístico
Exemplo
Função programa estendida (para AFNs)
Considerações finais
Linguagem rejeitada
A linguagem rejeitada por M é denotada por:
REJEITA(M)
é o conjunto de todas as palavras pertencentes a Σ∗ rejeitadas por
M a partir de {q0 }, ou seja:
REJEITA(M) = {w | δ ∗ ({q0 }, w ) ∩ F = ∅}
16 / 23
Uma palavra sobre não determinismo
Autômato finito não determinístico
Exemplo
Função programa estendida (para AFNs)
Considerações finais
Importante. . .
O não determinismo pode ser visto como uma “facilidade” que
nem sempre aumenta o poder de reconhecimento dessa classe de
autômatos.
Tipo 0
Tipo 1
Importante generalização –
então todo AFD é automati- Tipo 2
camente um AFN (Sipser
ipo
T
2012).
3
Conforme será mostrado,
qualquer AFN pode ser
simulado por um AFD.
17 / 23
Uma palavra sobre não determinismo
Autômato finito não determinístico
Exemplo
Função programa estendida (para AFNs)
Considerações finais
Exercícios (2)
Considerando o alfabeto Σ = {a, b, c}:
Exercício Â: Construa um AFN que aceita palavras cujo último
símbolo tenha aparecido anteriormente, e.g., aba é uma palavra
aceita pelo AFN, cacab não é aceita.
Exercício Ã: Considerando o AFN do exercício anterior, descreva
computação da palavra abbca a partir do estado inicial do autômato
(usando a função programa estendida, i.e. δ ∗ ).
18 / 23
Exercícios (3): agora vamos tentar resolver algo
ligeiramente mais complexo. . .
Considerando o alfabeto Σ = {1, 2, 3}, crie um AFN que aceita a
linguagem descrita a seguir.
Exercício Ä: L = {w : tal que o último símbolo de w aparece pelo
menos duas vezes, porém nenhum símbolo maior aparece entre as
duas últimas ocorrências de tal símbolo.
+ Exemplos de palavras que devem ser aceitas pelo AFN: 11, 2112,
123113, 3212113, etc.
Solução:
Exercícios (3): agora vamos tentar resolver algo
ligeiramente mais complexo. . .
Considerando o alfabeto Σ = {1, 2, 3}, crie um AFN que aceita a
linguagem descrita a seguir.
Exercício Ä: L = {w : tal que o último símbolo de w aparece pelo
menos duas vezes, porém nenhum símbolo maior aparece entre as
duas últimas ocorrências de tal símbolo.
+ Exemplos de palavras que devem ser aceitas pelo AFN: 11, 2112,
123113, 3212113, etc.
Solução:
q1
1 1
1
início
q0 2 q2 2 qf
1, 2
1, 2, 3 3 3
q3
Uma palavra sobre não determinismo
Autômato finito não determinístico
Exemplo
Função programa estendida (para AFNs)
Considerações finais
1 Uma palavra sobre não determinismo
2 Autômato finito não determinístico
3 Exemplo
Definição formal
4 Função programa estendida (para AFNs)
5 Considerações finais
20 / 23
Uma palavra sobre não determinismo
Autômato finito não determinístico
Exemplo
Função programa estendida (para AFNs)
Considerações finais
Considerações finais. . .
Na aula de hoje nós vimos:
Autômatos finitos não determinísticos (AFNs);
Diferenças entres AFDs e AFNs;
Função de transição estendida (para AFNs).
Na próxima aula: equivalência entre AFDs e AFNs.
21 / 23
Referências
Menezes, Paulo Blauth (2011). Linguagens Formais e Autômatos.
6th ed. Livros Didáticos Informática da UFRGS. Bookman, p. 256.
Sipser, Michael (2012). Introduction to the Theory of Computation.
3rd ed. Cengage Learning, p. 480.
,Próxima aula: exercício(s) sobre o conteúdo da aula de hoje! ,
Exercício Extra
- Considerando o alfabeto Σ = {1, 0}, crie um AFN que aceita
palavras da seguinte forma:
terminam em 01 e têm 011 como subpalavra; ou
terminam em 10 e têm 100 como subpalavra.
Exercício Extra
- Considerando o alfabeto Σ = {1, 0}, crie um AFN que aceita
palavras da seguinte forma:
terminam em 01 e têm 011 como subpalavra; ou
terminam em 10 e têm 100 como subpalavra.
0, 1
início
q0 0 q1 1 q2 1 q3 0 q4 1 q5
1
0, 1 q6 0 q7 0 q8 1 q9 0 q10
0, 1