Vai alla Home Page About me Courseware Federica Living Library Federica Virtual Campus 3D Le Miniguide all'orientamento Gli eBook di Federica
 
 
Il Corso Le lezioni del Corso La Cattedra
 
Materiali di approfondimento Risorse Web Il Podcast di questa lezione

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 Gcomp

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.

Figura A: Automa G.
Figura B: Automa complemento di .
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 G1 X G2

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

e

\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

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

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 E1∪ E2

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 Ei

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\}

Figura A
Figura B
Figura C

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.

I materiali di supporto della lezione

Paragrafi 2.3 (fino al sottoparagrafo 2.3.2 compreso) e 2.4 (fino a sottoparagrafo 2.4.2 compreso) da Cassandras-Lafortune.

  • Contenuti protetti da Creative Commons
  • Feed RSS
  • Condividi su FriendFeed
  • Condividi su Facebook
  • Segnala su Twitter
  • Condividi su LinkedIn
Progetto "Campus Virtuale" dell'Università degli Studi di Napoli Federico II, realizzato con il cofinanziamento dell'Unione europea. Asse V - Società dell'informazione - Obiettivo Operativo 5.1 e-Government ed e-Inclusion