Vai alla Home Page About me Courseware Federica Living Library Federica Virtual Campus 3D Le Miniguide all'orientamento Gli eBook di Federica
 
I corsi di Ingegneria
 
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