Autômatos Finitos Não-Determinísticos

Autômatos, Linguagens e Computação

Pontifícia Universidade Católica de Campinas

Prof. Dr. Denis M. L. Martins

Objetivos de Aprendizagem

  • Compreender e formalizar a estrutura de um Autômato Finitos Não-Determinístico (AFN), identificando seus componentes
  • Reconhecer as diferenças conceituais entre AFD e AFN.
  • Transpor um AFN para seu equivalente AFD.

Não‑Determinismo

  • A máquina pode estar em mais de um estado ao mesmo tempo.
  • Motivação histórica: A ideia de processamento paralelo.
  • Propriedade chave: Existência de caminhos alternativos que podem levar à aceitação.

Exemplo de AFN na lousa

Transição

  • Em determinado passo, a máquina pode escolher entre várias transições ou permanecer em estado sem consumir símbolo
  • Todo AFN é um -AFN.

Definição Formal de AFN

Um AFN é uma 5‑upla onde:

  • conjunto finito de estados.
  • alfabeto finito.
  • .
  • estado inicial.
  • conjunto de estados finais.

Função de Transição Estendida em AFN

Definição formal: Dado um AFN , a função de transição estendida , definida como

para, e .


Função de Transição Estendida em AFN (cont)

Podemos também estender a função de transição para conjuntos de estados com :

Assim, temos que:


Ou seja, a união de todas as possibilidades de aplicação da função de transição sobre a cadeia .

Aceite de cadeia em AFN

Dizemos que uma cadeia é aceita por um AFN se existir pelo menos uma sequência de transições que leva a um estado de aceitação (final) ao processar todos os símbolos de .

.


  • Imagine que o AFN assume múltiplas cópias de si mesmo, seguindo todas as possibilidades em paralelo.
  • "Always guesses right"

Linguagem de um AFN

A linguagem de um AFN é

Não-determinismo é uma
generalização do determinismo.

AFD e AFN são equivalentes

Equivalência

  • Número de estados de um AFD pode ser exponencial no número de estados de um AFN.
  • A linguagem dos AFNs são linguagens regulares.

Exercícios

  1. Mostre que a linguagem pode ser reconhecida por um AFN com apenas 2 estados.
  2. Projete um AFN que reconheça a linguagem:
  3. Projete um AFN que reconheça a linguagem:

Resumo e Próximos Passos

  • Definição Formal: AFN
  • A máquina pode estar em mais de um estado ao mesmo tempo.
  • Inspirado na ideia de processamento paralelo.
  • Transições que permitem "pular" sem consumir símbolo.
  • Equivalência com AFD (poderia ser reconhecida por um AFD).

center

Atividade recomendada: Leitura da seção 2.3 do capítulo 2.

Perguntas e Discussão

  • Qual é a vantagem prática de usar um AFN em vez de converter imediatamente para um AFD?
  • Em que situações o não‑determinismo pode simplificar drasticamente a construção do autômato?
  • Como a estrutura do AFN (por exemplo, presença de muitas transições ) influencia o tamanho final do AFD?
  • Quais linguagens não reconhecíveis por AFN?

# 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.