Home

Federica EU

1/29

Gianmaria De Tommasi » 3.Operazioni sugli automi e linguaggi regolari

Sommario della lezione

Operazioni sugli automi

Operazioni unarie

Operazioni binarie

Software UMDES

Linguaggi regolari e automi a stati finiti

Linguaggi regolari e loro proprietà

Espressioni regolari

Teorema di Kleene

Operazioni unarie

Dato un singolo automa $G = \bigl(X\,,E\,,f\,,\Gamma\,,x_0\,,X_m\bigr)$ è possibile definire le seguenti operazioni unarie:

parte accessibile di G – $Ac(G)$
parte coaccessibile di G – $CoAc(G)$
rifinitura di G – $Trim(G)$
automa complemento di G – $G^{comp}$

Parte Accessibile

Dato un automa
$G = \bigl(X\,,E\,,f\,, x_0\,,X_m\bigr)$ , la parte accessibile è l’automa

$Ac\bigl(G\bigr) := \bigl(X_{ac}\,,E\,,f_{ac}\,, x_0\,,X_{ac\,,m}\bigr)$

con

$X_{ac}=\bigl\{x\inX\ |\ \exists\ s\in E^\ast\ f(x_0\,,s)=x\bigr\}$
$X_{ac\,,m} = X_m\cap X_{ac}$
$f_{ac}=f_{|X_{ac}\times E\mapsto X_{ac}}$

Un automa G si dice accessibile se Ac(G) = G.

La parte accessibile non modifica ne il linguaggio generato ne quello marcato.

Parte CoAccessibile

Dato un automa
$G = \bigl(X\,,E\,,f\,, x_0\,,X_m\bigr)$ , la parte coaccessibile è l’automa
$<br /> CoAc\bigl(G\bigr) := \bigl(X_{coac}\,,E\,,f_{coac}\,, x_{0_{coac}}\,,X_m\bigr)$

con

$X_{coac}=\bigl\{x\inX\ |\ \exists\ s\in E^\ast\ f(x\,,s)\in X_m\bigr\}$
$x_{0_{coac}} =x_0$ se $x_0\in X_{coac}$ , altrimenti non è definito
$f_{coac}=f_{|X_{coac}\times E\mapsto X_{coac}}$

Quando si esegue la parte coaccessibile si modifica il linguaggio generato (in particolare si possono eliminare alcune stringhe da $\mathcal{L}\bigl(G\bigr)$

Un automa G si dice COACCESSIBILE se CoAc(G) = G. In questo caso risulta
$\mathcal{L}\bigl(G\bigr)=\overline{\mathcal{L}_m\bigl(G\bigr)}$

Rifinitura

Dato un automa
$G = \bigl(X\,,E\,,f\,, x_0\,,X_m\bigr)$ , la sua rifinitura (o trim) è l’automa

$Trim(G):= CoAc\Bigl(Ac\bigl(G\bigr)\Bigr) = Ac\Bigl(CoAc\bigl(G\bigr)\Bigr)$

Per definizione un automa rifinito è sia accessibile che coaccessibile

Automa Complemento

Si consideri un automa rifinito $G = \bigl(X\,,E\,,f\,, \Gamma\,,x_0\,,X_m\bigr)$ . Se $\mathcal{L}_m\bigl(G\bigr) =L$ , essendo $G$ coaccessibile, vale $\mathcal{L}\bigl(G\bigr)=\bar{L}$ .

L’automa complemento di $G$ si indica con $G^{comp}$ ed è un automa per cui

$\mathcal{L}_m\bigl(G^{comp}\bigr)=E^\ast\setminus L$

Algoritmo per la costruzione di G^comp

Dato $G=\bigl(X\,,E\,,f\,, \Gamma\,,x_0\,,X_m )$ rifinito:

1. completare la funzione di transizione $f(\cdot\,,\cdot)$

$f_{tot}(x\,,e):=\left\{\begin{array}{ll}f(x\,,e)& \mathrm{se}\ e\in\Gamma(x)\\ x_d&\mathrm{altrimenti}\end{array}\right.$

con $x_d\notin X_m$ e $f_{tot}(x_d\,,e)=x_d\ \forall\ e\in E$

2. Sia $X^{new}_m=\Bigl(X\cup\{x_d\}\Bigr)\setminus X_m$ e $G^{comp}=\iggl(X\cup\{x_d\}\,,E\,,f_{tot}\,,x_0\,,X^{new}_m\bigr)$

Per costruzione, si ha che

$\mathcal{L}\bigl(G^{comp}\bigr) = E^\ast$

$\mathcal{L}_m\bigl(G^{comp}\bigr) = E^\ast\setminus \mathcal{L}_m\bigl(G\bigr)$

Esempio

In Figura A: Automa G con $E=\bigl\{a\,,b\,,c\bigr\}$ .
In Figura B: Automa complemento di $Trim\bigl(G\bigr)$ .
In Figura C: Automa rifinito.

Operazioni binarie

Dati due automi $G_1 = \bigl(X_1\,,E_1\,,f_1\,,\Gamma_1\,,x_{0_1}\,,X_{m_1}\bigr)$ e $G_2 = \bigl(X_2\,,E_2\,,f_2\,,\Gamma_2\,,x_{0_2}\,,X_{m_2}\bigr)$ si definiscono le seguenti operazioni binarie:

prodotto – $G_1\times G_2$
prodotto parallelo (o sincrono) – $G_1\| G_2$

Prodotto G₁ X G₂

Dati due automi $G_1$ e $G_2$ l’automa prodotto $G_1\times G_2$ è dato da
$G_1\times G_2:=Ac\bigl(X_1\times X_2\,,E_1\cap E_2\,,f\,,\Gamma_{1\times 2}\,,(x_{0_1)\,,x_{0_2})\,,X_{m_1}\times X_{m_2}\bigr)$

con

e
$\Gamma_{1\times 2}(x_1\,,x_2)=\Gamma_1(x_1)\cap\Gamma_2(x_2)$

Un evento occorre in $G_1\times G_2$ se e solo se occorre in entrambi gli automi $G_1$ e $G_2$

Linguaggi “parlati” da $G_1\times G_2$

Si può facilmente verificare che

$\mathcal{L}\bigl(G_1\times G_2\bigr)=\mathcal{L}\bigl(G_1\bigr)\cap\mathcal{L}\bigl(G_2\bigr)$

e che

$\mathcal{L}_m\bigl(G_1\times G_2\bigr)=\mathcal{L}_m\bigl(G_1\bigr)\cap\mathcal{L}_m\bigl(G_2\bigr)$

Quindi l’intersezione di due linguaggi $L_1$ e $L_2$ può essere implementata effettuando il prodotto dei due automi che li generano

Osservazione

Se $E_1\cap E_2=\emptyset$ allora

$\mathcal{L}\bigl(G_1\times G_2\bigr) = \bigl\{\varepsilon\bigr\}$

e se $(x_{0_1}\,,x_{0_2})\inX_{m_1}\times X_{m_2}$ allora

$\mathcal{L}_m\bigl(G_1\times G_2\bigr) = \bigl\{\varepsilon\bigr\}$

Altrimenti

$\mathcal{L}_m\bigl(G_1\times G_2\bigr) = \emptyset$

Prodotto parallelo $G_1\| G_2$

Dati due automi $G_1$ e $G_2$ l‘automa prodotto parallelo (o prodotto sincrono) $G_1\| G_2$ è dato da

$G_1\| G_2:=Ac\bigl(X_1\times X_2\,,E_1\cup E_2\,,f\,,\Gamma_{1\| 2}\,,(x_{0_1)\,,x_{0_2})\,,X_{m_1}\times X_{m_2}\bigr)$

con

$f\bigl((x_1\,,x_2)\,,e\bigr):=\left\{\begin{array}{ll}\Bigl(f_1(x_1\,,e)\,,f_2(x_2\,,e)\Bigr) &mathrm{se}\ e\in\Gamma_1(x_1)\cap\Gamma_2(x_2)\\ \Bigl(f_1(x_1\,,e)\,,x_2\Bigr) & \mathrm{se}\ e\in\Gamma_1(x_1)\setminus E_2\\ \Bigl(x_1\,,f_2(x_2\,,e)\,,x_2\Bigr) & \mathrm{se}\ e\in\Gamma_2(x_2)\setminus E_1\\ \mathrm{non\ definita) &\mathrm{altrimenti}\end{array}\right$

$\Gamma_{1\| 2}(x_1\,,x_2)=\Bigl[\Gamma_1(x_1)\cap\Gamma_2(x_2)\Bigr]\cup\Bigl[\Gamma_1(x_1)\setminus E_2\Bigr]\cup\Bigl[\Gamma_2(x_2)\setminus E_1\Bigr]$

Osservazioni

Se $E_1=E_2$ allora $G_1\| G_2=G_1\times G_2$

Se $E_1\cap E_2=\emptyset$ allora $G_1\| G_2$ equivale all’evoluzione parallela (non sincronizzata) dei due automi

Proiezione

$P_i:\bigl(E_1\cup E_2\bigr)^\ast\mapsto E_i^\ast$

$\left\{\begin{array}{ll}P_i(\varepsilon):=\varepsilon & \\ P_i(e):=e & \mathrm{se}\ e\in E_i\\ P_i(e):=\varepsilon & \mathrm{se}\ e\notin E_i\\ P_i(se):=P_i(s)P_i(e) & s\in\bigl(E_1\cup E_2\bigr)^\ast\,, e\in\bigl(E_1\cup E_2\bigr) \end{array} \right.$

Proiezione inversa

$P^{-1}_i:E_i^\ast\mapsto 2^{\bigl(E_1\cup E_2\bigr)^\ast}$

$P^{-1}_i(t):=\Bigl\{s\in\bigl(E_1\cup E_2\bigr)^\ast\ :\ P_i(s)=t \Bigr\}$

Proiezioni su linguaggi

Estensione dell’operazione di proiezione ai linguaggi

Sia L un linguaggio definito dall’insieme di eventi E₁∪ E₂

$P_i (L) : = \{ t{_i}{^*} : \exists s \in L, P_i(s) = t }$

Sia $L_i \leq E {_i}{^*}$ un linguaggio definito dall’insieme di eventi E_i

$P{_i} {^{-1}} (L_i) : = \{ s \in (E_1 \cup E_2)^* : \exists t \in L_i,,P_i (s) = t \}$

Si noti che $P_i (P{_i} {^{-L}} (L)) = L_e ~~~L \leq P{_i} {^{-1}} (P_i (L))$

Proiezioni – Esempi

Siano $E_1=\bigl\{a\,,b\bigr\}$ , $E_2=\bigl\{b\,,c\bigr\}$ e

$L=\bigl\{c\,,ccb\,,abc\,,cacb\,,cabcbbca\bigr\}$

allora

$P_1\bigl(L\bigr)=\bigl\{\varepsilon\,,b\,,ab\,,abbba\bigr\}$
$P_2\bigl(L\bigr)=\bigl\{c\,,ccb\,,bc\,,cbcbbc\bigr\}$
$P^{-1}_1\Bigl(\bigl\{\varepsilon\bigr\}\Bigr)=\bigl\{c\bigr\}^\ast$
$P^{-1}_1\Bigl(\bigl\{ab\bigr\}\Bigr)=\bigl\{c\bigr\}^\ast\bigl\{a\bigr\}\bigl\{c\bigr\}^\ast\bigl\{b\bigr\}\bigl\{c\bigr\}^\ast$
$P^{-1}_1\biggl(P_1\Bigl(\bigl\{abc\bigr\}\Bigr)\biggr)=P^{-1}_1\Bigl(\bigl\{ab\bigr\}\Bigr)\supset\bigl\{abc\bigr\}$

Linguaggi associati all’automa prodotto parallelo

Linguaggio generato

$\mathcal{L}\bigl(G_1\| G_2\bigr)=P^{-1}_1\Bigl(\mathcal{L}\bigl(G_1\bigr)\Bigr)\cap P^{-1}_2\Bigl(\mathcal{L}\bigl(G_2\bigr)\Bigr)$

Linguaggio marcato

$\mathcal{L}_m\bigl(G_1\| G_2\bigr)=P^{-1}_1\Bigl(\mathcal{L}_m\bigl(G_1\bigr)\Bigr)\cap P^{-1}_2\Bigl(\mathcal{L}_m\bigl(G_2\bigr)\Bigr)$

In generale vale

$P_i\Bigl(\mathcal{L}\bigl(G_1\| G_2\bigr)\Bigr)\subseteq\mathcal{L}\bigl(G_i\bigr)\,, i=1\,,2$

Esempi

In Figura A: Automa $G_1$ con $E_1=\bigl\{a\,,b\,,c\bigr\}$ .
In Figura B: Automa $G_2$ con $E_2=\bigl\{b\,,c\bigr\}$ .
In Figura C: Automa $G_1\| G_2$
$\mathcal{L}\bigl(G_1\bigr)=\bigl\{\varepsilon\,,a\,,ab\,,abc\,,abca\,,\ldots\bigr\}$
$\mathcal{L}\bigl(G_2\bigr)=\bigl\{\varepsilon\,,b\,,bc\,,bb\,,cc\,,bbb\,,ccc\,,\ldots\bigr\}$
$\mathcal{L}\bigl(G_1\| G_2\bigr)=\bigl\{\varepsilon\,,a\,,ab\,,abc\,,abca\bigr\}$

Composizione parallela tra linguaggi

È possibile estendere l’operazione di prodotto parallelo dagli automi ai linguaggi. In particolare la composizione parallela tra linguaggi è definita come

$L_1\| L_2:= P^{_1}_1\bigl(L_1\bigr)\cap P^{-1}_2\bigl(L_2\bigr)$

UMDES

UMDES Software Library

UMDES è una libreria C sviluppata dal DES Group dell’Università del Michigan. UMDES mette a disposizione una serie di funzioni per effettuare operazioni sugli automi.

L’homepage del progetto è http://www.eecs.umich.edu/umdes/toolboxes.html

Gli automi possono essere specificati in maniera interattiva oppure utilizzando un file testo

Le funzioni di UMDES possono essere richiamate da riga di comando

Un lista dei comandi e dei formati dei file si trova qui, mentre un rapida guida si trova qui.

UMDES – Esempio di file .fsm

Utilizzando UMDES gli automi possono essere specificati in file testo con estensione .fsm (finite state machine)

Un esempio di file .fsm per l’automa riportato in figura è il seguente

4 ← numero di stati

I 1 1 (nome stato, flag stato marcato, numero di archi in uscita)
s W c o (evento in uscita, stato destinazione, flag controllabilità, flag osservabilità)

W 0 1
f A uc o

A 0 1
t T c o

T 0 1
ft I uc o

Comandi UMDES

Operazioni unarie

acc →parte accessibile
co_acc →_parte coaccessibile
trim→rifinitura
comp_fsm →automa complemento

Operazioni binarie

product →prodotto
par_comp →prodotto parallelo

Automi a stati finiti e linguaggi

Dato un linguaggio $L$ è sempre possibile costruire un automa $G$ tale che $\mathcal{L}\bigl(G\bigr)=L$ oppure $\mathcal{L}_m\bigl(G\bigr)=L$

Se consideriamo solo automi con spazio di stato finito (automi a stati finiti), allora l’affermazione precedente non è più vera!

Esempio: $L=\bigl\{a^nb^n\ :\ n\ge 0\bigr\}$ non può essere ne generato ne marcato da un automa a stati finiti

Linguaggi regolari

Definizione di linguaggio regolare

Un linguaggio $L$ si dice regolare se può essere marcato da un automa a stati finiti

La classe dei linguaggi regolari si indica con $\mathcal{R}$ e si ha

$\mathcal{R}\subset 2^{E^\ast}$

Proprietà dei linguaggi regolari

Siano $L_1\,,L_2\in\mathcal{R}$ , allora

$\bar{L_1}\in\mathcal{R}$
$L_1^\ast\in\mathcal{R}$
$L^c:=E^\ast\setminus L_1 \in\mathcal{R}$
$L_1\cup L_2\in\mathcal{R}$
$L_1\cap L_2\in\mathcal{R}$
$L_1L_2\in\mathcal{R}$

Espressioni regolari

Indicando con + l’unione di due stringhe e con $a^ast =\bigl\{\varepsilon\,,a\,,aa\,,aaa\,,\ldots\bigr\}$ , è possibile definire le espressioni regolari come segue:

1. $\emptyset\,,\bigl\{\varepsilon\bigr\}~~~ e ~~~\bigl\{a\bigr\}$ sono espressioni regolari
2. se $r$ e $s$ sono espressioni regolari lo sono anche

$rs$
$r+s$
$r^\ast$
$s^\ast$

3. Le espressioni regolari sono solo quelle che possono essere definite mediante le regole 1 e 2.

Teorema di Kleene

Ogni linguaggio che può essere espresso mediante un’espressione regolare è un linguaggio regolare. Viceversa, ogni linguaggio regolare può essere rappresentato mediante un’epsressione regolare.