Um AFN é uma 5‑upla
Definição formal: Dado um AFN
para,
Podemos também estender a função de transição para conjuntos de estados
Assim, temos que:
Ou seja, a união de todas as possibilidades de aplicação da função de transição sobre a cadeia
Dizemos que uma cadeia
A linguagem de um AFN
Não-determinismo é uma
generalização do determinismo.
AFD e AFN são equivalentes
Atividade recomendada: Leitura da seção 2.3 do capítulo 2.
# Exemplos Ilustrativos 1. **Linguagem L = { w ∈ {a,b}* | w contém “ab” }** - AFN simples com ε‑transição que “pula” para reconhecer a sequência "ab" em qualquer posição. 2. $L = (a + b)*(aa) (a + b)\$ - Um estado de transição que pode escolher entre 'a' ou 'b', depois requer duas ocorrências consecutivas de ‘a’. > *Para cada exemplo, desenhe o grafo na próxima slide.* --- ## Slide 7 – Construção de AFN a partir de Expressões Regulares (Algoritmo de Thompson) 1. **Base**: Para $a \in \Sigma$, construir um automato com dois estados e transição $q_0 \xrightarrow{a} q_1$. 2. **Operador Kleene**: Adicionar ε‑transições que permitem “repetir” o sub‑AFN arbitrariamente. 3. **Concatenação**: Conectar estado final do primeiro AFN ao inicial do segundo via ε‑transição. 4. **Alternância (Union)**: Criar novos estados iniciais e finais, conectando-os aos sub‑AFNs por ε‑transições. --- ## Slide 8 – Conversão de AFN para AFD (Subconjunto Construtivo) - **Passo 1**: Calcular a *ε‑fechadura* $\varepsilon\text{-closure}(S)$. - **Passo 2**: Para cada conjunto $S$ e símbolo $a$, definir $T = \bigcup_{q \in S} \delta(q,a)$ e depois $\varepsilon\text{-closure}(T)$. - **Resultado**: Cada subconjunto de estados se torna um estado do AFD. > *Demonstração passo a passo no próximo slide.* --- ## Slide 9 – Exercício Prático (Em Sala) Construa, utilizando o algoritmo de Thompson, um AFN que reconheça a linguagem \[ L = \{\, w \in \{0,1\}^* \mid |w| \text{ é múltiplo de } 3 \,\}. \] **Pistas**: - Use três estados $q_0, q_1, q_2$. - Transições: $q_i \xrightarrow{0/1} q_{(i+1) \bmod 3}$. - Estado inicial e final são $q_0$. --- ## Slide 10 – Propriedades Teóricas de AFN | Propriedade | Tese | |-------------|------| | **Equivalência com AFD** | Toda linguagem reconhecida por um AFN pode ser reconhecida por um AFD (pelo algoritmo de subconjunto). | | **Complexidade da Conversão** | O AFD resultante pode ter até $2^{|Q_{AFN}|}$ estados. | | **Decidibilidade** | Problemas como aceitação, vazios e equivalência são decidíveis para AFNs. | ---
## Slide 12 – Questão de Prova (Modelo) > **Enunciado**: Considere o AFN $\mathcal{A} = (Q,\Sigma,\delta,q_0,F)$ com > $Q=\{q_0,q_1,q_2\}$, $\Sigma=\{a,b\}$, > \[ > \begin{aligned} > &\delta(q_0,a)=\{q_0,q_1\}, \quad \delta(q_0,\varepsilon)=\{q_2\} \\[4pt] > &\delta(q_1,b)=\{q_1\}, \quad \delta(q_2,a)=\{q_2\} > \end{aligned} > \] > $F=\{q_1\}$. > a) Desenhe o grafo de $\mathcal{A}$. > b) Determine se a palavra “aba” pertence à linguagem reconhecida. > c) Construa um AFD equivalente usando o algoritmo de subconjunto.