Generic Non deterministic Finite state Automaton (GNFA)

Un Generic Non deterministic Finite state Automaton è una tupla $N=(Q,\Sigma ,\delta ,q_{\text{start}},q_{\text{accept}})$, dove $\delta :Q\setminus \{q_{\text{accept}}\}\times Q\setminus \{q_{\text{start}}\}\to \text{re}(\Sigma )=\mathcal{R}$.

Accettazione: un GNFA accetta $w\in {\Sigma }^{\star }$ se $w=w_1,\dots ,w_k(w_i\in \Sigma )$ ed:

$\exists q_0,\dots ,q_k\text{t.c.}$:

• $q_0=q_{\text{start}}\wedge q_k=q_{\text{accept}}$
• $\forall i=1\dots k{w}_i\in L(R_i)\wedge R_i\in \text{re}(\Sigma )\wedge R_i=\delta (q_{i-1},q_i)$

Conversione NFA $\to$ GNFA

Dato un qualsiasi automa non deterministico a stati finiti (NFA) è facile ottenere un GNFA equivalente.

Ad esempio questo NFA

Può essere convertito in questo GNFA

Algoritmo $\text{Convert}(G)$

Sia $k$ il numero di stati di $G$.

• Se $k=2$, ci sono solo $q_{\text{start}}$ e $q_{\text{accept}}$ e l’arco $\delta (q_{\text{start}},q_{\text{accept}})=R\in \text{re}(\Sigma )$. Output: $R$.
• Se $k>2$, scelgo $q_{\text{rappresentante}}\in Q\setminus \{q_{\text{start}},q_{\text{accept}}\}\forall q_i\in Q^{\prime }$.
  • Creo un GNFA $G^{\prime }=(Q\setminus \{q_{\text{rappresentante}}\},\Sigma ,{\delta }^{\prime },q_{\text{start}},q_{\text{accept}})$
  • $\forall q_i\in Q^{\prime }\setminus \{q_{\text{accept}}\},q_j\in Q^{\prime }\setminus \{q_{\text{start}}\}{\delta }^{\prime }(q_i,q_j)$ (si costruisce ${\delta }^{\prime }$ progressivamente, seguendo la forma canonica degli NFA)

${\delta }^{\prime }(q_i,q_j)=(R_1)(R_2{)}^{\star }(R_3)\cup R_4$

Affermazione: $\forall \text{GNFA}G,G^{\prime }=\text{Convert}(G)$ è equivalente a $G$. Cioè l’etichetta finale $R$ tale che $R=\delta (q_{\text{start}},q_{\text{accept}})$ è l’espressione regolare equivalente al GNFA $G$ di partenza.

Dimostrazione:

• $k=2$ è banale.
• caso induttivo: suppongo vera l’affermazione per GNFA con $k$ stati, è vero pure per $k+1$ stati.

Dimostriamolo per $k$ stati.

Ma in effetti:

• se $G$ accetta $w$, ci sarà ramo di computazione che attraversa $q_{\text{start}},\dots ,q_{\text{accept}}$. Due casi:
  • $q_{\text{rappresentante}}$ non è uno degli stati intermedi allora non è cambiato nulla ($R_4$ è compreso nell’unione).
  • $q_{\text{rappresentante}}$ è uno degli stati intermedi: è ok per lo stesso motivo ma relativo a $R_1(R_2{)}^{\star }{R}_3$ ovvero tutti i modi per andare da $q_i$ a $q_j$ passando per $q_{\text{rappresentante}}$.

$\square$

Esercizi

1. Trasformare $(ab\cup a{)}^{\star }$ in NFA.

2. Trovare l’espressione regolare equivalente al seguente NFA

$$\Sigma =\{0,1,2\}$$