Construção de um AFND-ε a partir de uma gramática

---

Dada uma gramática $G=(V,T,P,S)$ do tipo GLUD, podemos construir um AFND-ε (Autômato Finito Não Determinístico com transições-ε) $M=(\Sigma ,Q,\delta ,q\_0,F)$ da seguinte forma:

• $\Sigma =T$ (alfabeto igual ao conjunto de terminais da gramática).
• $Q=V\cup q_f$, onde $q_f\notin V$ (um novo estado final).
• $F=q_f$ (conjunto de estados finais).
• $q_0=S$ (o estado inicial é o símbolo inicial da gramática).

As produções da gramática são convertidas em transições no autômato conforme:

Produção	Transição
$A\to \epsilon$	$\delta (A,\epsilon )=q_f$
$A\to a$	$\delta (A,a)=q_f$
$A\to B$	$\delta (A,\epsilon )=B$
$A\to aB$	$\delta (A,a)=B$

Exemplo:

Gramática: $G=(\{S,A,B\},\{a,b\},P,S)$ Produções:

• $S\to aA$
• $A\to bB\mid \epsilon$
• $B\to aA$

Autômato: $M=(\{a,b\},\{S,A,B,q_f\},\delta ,S,\{q_f\})$

Transições:

Produção	Transição
$S\to aA$	$\delta (S,a)=A$
$A\to bB$	$\delta (A,b)=B$
$A\to \epsilon$	$\delta (A,\epsilon )=q_f$
$B\to aA$	$\delta (B,a)=A$

Diagrama de estados: $S⟶A⟶B⟶A⟶q_f$ (com transições conforme as produções).

Referências

---

Aula de Gramática Regular