Autômatos Finitos Não-determinísticos com Movimentos Vazios - DIM0606

Índice da seção

$λ$ -Autômatos Finitos Não-determinísticos
- Definição: $λ$ -Autômato Finito Não-determinístico
  - Exemplo 01
  - Exemplo 02
- Computação em $λ$ -Autômatos Finitos Não-determinísticos

$λ$ -Autômatos Finitos Não-determinísticos

Os $λ$ -Autômatos Finitos Não-determinísticos (podendo também ser chamados de Autômatos Finitos Não-determinísticos com Movimentos Vazios) são como uma generalização do modelo de AFN. Entretanto, diferentes dos AFNs, o modelo $λ$ -AFN nos permite ter transições entre estados diferentes usando (ou consumindo) a palavra vazia, as chamadas $λ$ -transições.

Definição: $λ$ -Autômato Finito Não-determinístico

Um $λ$ -Autômato Finito Não-determinístico ( $λ$ -AFN) é uma estrutura $A = ⟨ Q, Σ, \underline{δ_{N}}, q_{0}, F ⟩,$ onde:

$Q$ é um conjunto não-vazio e finito de estados internos.
$Σ$ é um alfabeto de entrada.
$\underline{δ_{N}} : Q \times (Σ \cup {λ}) \to ℘ (Q)$ é uma função total de transição.
$q_{0} \in Q$ é o estado inicial.
$F \subseteq Q$ é o conjunto de estados finais ou de aceitação.

Convencionalmente chamamos $\underline{δ_{N}}$ de $λ$ -Função de Transição Não-determinística.

Exemplo 01

A estrutura $A = ⟨{q_{0}, q_{1}, q_{2}}, {0, 1}, \underline{δ_{N}}, q_{0}, {q_{0}}⟩$ , com $\underline{δ_{N}}$ sendo especificada como no grafo abaixo, é um $λ$ -AFN.

Exemplo 02

A estrutura $A = ⟨{q_{0}, q_{1}, q_{2}}, {0, 1}, \underline{δ_{N}}, q_{0}, {q_{2}}⟩$ , com $\underline{δ_{N}}$ sendo especificada como no grafo abaixo, é um $λ$ -AFN.

Uma interpretação para as transições da forma $\underline{δ_{N}} (q, λ) = X \in Q$ é que a unidade de controle do autômato consegue mudar do seu estado atual interno $q$ para um subconjunto de estados $X$ sem necessidade de acessar a memória do autômato.

Computação em $λ$ -Autômatos Finitos Não-determinísticos

Note que a definição da função de transição $\underline{δ_{N}}$ somente nos garante que as transições ocorrem apenas em duas situações, a primeira em relação a leitura de símbolos individuais de $Σ$ e a segunda em relação a palavra vazia, isto é, ainda não há uma forma de computar uma palavra $w$ , com $∣ w ∣ > 1$ . A saída para contornar essa situação é similar ao que é feito para os AFDs e AFNs, isto é, precisaremos estender a função de transição do autômato.

Entretanto, nas definições anteriores, $λ$ não fazia parte do alfabeto de entrada, e por isso era possível utilizá-la para definir recursivamente as funções estendidas. No entanto, como agora precisamos incluir $λ$ explicitamente no processo, será necessário adotar um novo método para a definição das funções estendidas. Para isso serão necessárias mais alguns definições, como segue:

Definição: Função $δ_{λ}$

Seja $A = ⟨ Q, Σ, \underline{δ_{N}}, q_{0}, F ⟩$ um $λ$ -AFN. A função $δ_{λ} : Q \to ℘ (Q)$ é definida como $δ_{λ} (q) = i = 0 ⋃ n λ -fecho^{i} (q),$ onde $n = # Q - 1$ e $λ -fecho^{0} (q) λ -fecho^{i} (q) = {q} = q^{'} \in λ -fecho^{i - 1} (q) ⋃ \underline{δ_{N}} (q^{'}, λ) .$

Exemplo 03

Considere o $λ$ -AFN do Exemplo 02. Tem-se para o estado $q_{1}$ que $δ_{λ} (q_{1}) = i = 0 ⋃ 2 λ -fecho^{i} (q_{1}) = λ -fecho^{2} (q_{1}) \cup λ -fecho^{1} (q_{1}) \cup λ -fecho^{0} (q_{1})$ sabe-se que, $λ -fecho^{0} (q_{1}) = {q_{1}} .$ Desenvolvendo $λ -fecho^{2} (q_{1})$ , tem-se que $λ -fecho^{2} (q_{1}) = q^{'} \in λ -fecho^{1} (q_{1}) ⋃ \underline{δ_{N}} (q^{'}, λ)$ mas, $λ -fecho^{1} (q_{1}) = q^{'} \in λ -fecho^{0} (q_{1}) ⋃ \underline{δ_{N}} (q^{'}, λ) = q^{'} \in {q_{1}} ⋃ \underline{δ_{N}} (q^{'}, λ) = {q_{2}} .$ Assim, $λ -fecho^{2} (q_{1}) = q^{'} \in {q_{2}} ⋃ \underline{δ_{N}} (q^{'}, λ) = \underline{δ_{N}} (q_{2}, λ) = \emptyset$ Substituindo na segunda igualdade, temos que $δ_{λ} (q_{1}) = \emptyset \cup {q_{2}} \cup {q_{1}} = {q_{2}, q_{1}} .$

Com esta definição, podemos então capturar todos os estados que podem ser alcançados a partir de um dado estado $q$ por meio de transições $λ$ , incluindo transições indiretas, prevenindo a perda de estados acessíveis não diretamente conectados.

Mas, note que a definição acima só é aplicável para estados individuais. Como no não-determinísmo podemos estar simultaneamento em múltiplos estados, precisamos que essa função seja aplicável em um conjunto deles. Vejamos formalmente como segue...

Definição: Função $\hat{δ}_{λ}$

Seja $A = ⟨ Q, Σ, \underline{δ_{N}}, q_{0}, F ⟩$ um $λ$ -AFN. A função $\hat{δ}_{λ} : ℘ (Q) \to ℘ (Q)$ é definida como $\hat{δ}_{λ} (X) = q \in X ⋃ δ_{λ} (q) .$

Exemplo 04

Considere o $λ$ -AFN do Exemplo 01, tem-se para o conjunto ${q_{1}, q_{2}}$ que, $\hat{δ}_{λ} ({q_{1}, q_{2}}) = q \in {q_{1}, q_{2}} ⋃ δ_{λ} (q) = δ_{λ} (q_{1}) \cup δ_{λ} (q_{2}) = {q_{0}, q_{1}, q_{2}} \cup {q_{0}, q_{2}, q_{1}} = {q_{0}, q_{2}, q_{1}}$

E por fim, definidos $δ_{λ}$ e $\hat{δ}_{λ}$ , podemos estender nossa função de transição.

Definição: $λ$ -Função de Transição Não-determinística Estendida

Seja $A = ⟨ Q, Σ, \underline{δ_{N}}, q_{0}, F ⟩$ um $λ$ -AFN. A $λ$ -Função de Transição Não-determinística Estendida $\underline{\hat{δ}_{N}} : Q \times Σ^{*} \to ℘ (Q),$ é definida recursivamente como: $\underline{\hat{δ}_{N}} (q, λ) \underline{\hat{δ}_{N}} (q, w a) = δ_{λ} (q) = q^{'} \in \underline{\hat{δ}_{N}} (q, w) ⋃ \hat{δ}_{λ} (\underline{δ_{N}} (q^{'}, a)) .$

Keyboard shortcuts

DIM0606 - LINGUAGENS FORMAIS E AUTÔMATOS