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 » 2.Linguaggi ed Automi


Sommario della lezione

Linguaggi ed automi

  • Definizione di linguaggio
  • Operazioni sui linguaggi
  • Definizione di automa
  • Linguaggi associati agli automi
  • Esercizi proposti

Alfabeto e parole

Dato un sistema ad eventi discreti, l’insieme di tutti gli eventi che possono occorrere può essere visto come un alfabeto che indicheremo con
E=\bigl\{a\,,b\,,c\,,\ldtos\bigr\}\,,
con a, b, c, … eventi.

Una stringa o parola o traccia s è una sequenza di eventi s= e_1e_2e_3\,,

\varepsilon indica la sequenza vuota o stringa vuota.

La lunghezza di una stringa s si indica con |s| .
Per definizione |\varepsilon|= 0

Definizione di linguaggio

Definizione
Un linguaggio definito su un alfabeto E è un insieme (anche di cardinalità infinita) di parole di lunghezza finita formate con gli elementi di E .

Esempi

E=\bigl\{a,b,c\bigr\}

Linguaggio di cardinalità finita

L_1=\bigl\{\varepsilon\,,a\,,abb\bigr\}

Linguaggio di cardinalità infinita
L_2 = \bigl\{ tutte le parole di lunghezza finita che iniziano con c\bigr\}

Concatenazione tra stringhe

Concatenazione
L’operazione fondamentale per costruire parole è la concatenazione.

a concatenato b si indica con ab
ab concatenato b si indica con abb

\varepsilon rappresenta l’elemento identità rispetto all’operazione di concatenazione, infatti a\varepsilon = \varepsilon a = a

Chiusura di Kleene

Chiusura di Kleene

La chiusura di Kleene di un alfabeto E si indica con E^\ast ed è l’insieme di tutte le parole di lunghezza finita costruite con gli elementi di E, compresa la stringa vuota \varepsilon

Qualsiasi linguaggio definito su E è un sottoinsieme di E^\ast

Nomenclatura e notazione

Prefissi, sottostringhe e suffissi

Data una stringa s = tuv con t\,,u\,,v\in E^\ast, allora

  • t si dice PREFISSO di s
  • u si dice SOTTOSTRINGA di s
  • v si dice SUFFISSO di s

Notazione

Con a^n si indica la sequenza aaa\ldots a in cui a è ripetuto n volte

Operazioni sui linguaggi

Operazioni sugli insiemi

Essendo definiti come insiemi, sui linguaggi sono implicitamente definite le operazioni di Unione, Intersezione, Complemento e Differenza.

Operazioni peculiari dei linguaggi

  • Concatenazione
  • Chiusura rispetto ai prefissi
  • Chiusura di Kleen

Concatenazione di linguaggi

Siano L_a\,,\L_b \subseteq E^\ast

Allora si indica con

L_aL_b:=\bigl\{s\in E^\ast\ :\ s =s_as_b\ \mathrm{e}\ s_\in L_a\,, s_b\in L_b \bigr\}[

l’insieme ” L_a concatenato L_b

Chiusura rispetto ai prefissi

Sia L\subseteq E^\ast

Allora l’insieme

\bar{L}:=\bigl\{s\in E^\ast\ :\ \exists\ t\in E^\ast\ \mathrm{tale che}\ st\inL \bigr\}

è la chiusura rispetto ai prefissi di L

Un linguaggio si dice chiuso rispetto ai prefissi se L=\bar{L}

Chiusura di Kleene di un linguaggio

Sia L\subseteq E^\ast

Allora l’insieme

L^\ast:=\bigl\{\varepsilon\bigr\}\cupL \cup LL \cup LLL \cup \ldots

è la chiusura di Kleene di L

L’operatore ^\ast è idempotente, cioè \bigl(L^\ast\bigr)^\ast = L^\ast

Precedenze tra gli operatori

  1. Chiusura rispetto ai prefissi e chiusura di Kleene
  2. Concatenazione
  3. Operazioni su insiemi

Osservazioni

NOTA: \varepsilon\neq \emptyset

Pertanto \bigl\{\varepsilon\bigr\} è un linguaggio non vuoto contenente la stringa vuota!

  • Se L=\emptyset\Rightarrow \bar{L}=\emptyset
  • Se L\neq\emptyset\Rightarrow \varepsilon\in\bar{L}
  • \emptyset^\ast=\bigl\{\varepsilon\bigr\}
  • \bigl\{\barepsilon\bigr\}^\ast = \bigl\{\varepsilon\bigr\}

Esempi

E = \bigl\{a\,,b\,,c\bigr\}

L_1 = \bigl\{\varepsilon\,,a\,,abb\bigr\}

L_2 = \bigl\{c\bigr\}

  • L_1\neq\bar{L}_1 ~~perch\grave e ~~~ab\notin L_1
  • L_2\neq\bar{L}_2~~ perch \grave e~~\varepsilon\notin L_2
  • L_1L_2\bigl\{c,ac,abbc\bigr\}
  • \bar{L}_2 = \bigl\{\varepsilon\,,c\bigr\}
  • L_1^\ast = \bigl\{\varepsilon\,,a\,,abb\,,aa\,,aabb\,,abba\,,abbabb\,\ldots\bigr\}

Linguaggi e automi

  • Alcuni linguaggi possono essere specificati enumerando le parole che li compongono
  • Altri linguaggi possono essere specificati descrivendo “a parole” le caratteristiche delle loro stringhe
  • In generale è necessario disporre di un metodo formale di rappresentazione dei linguaggi, per poter disporre di strumenti di analisi sintesi dei SED

Definizione di automa

Automa

Un Automa Deterministico G è una 6-pla

G = \bigl(X\,,E\,,f\,,\Gamma\,,x_0\,X_m\bigr)

con:

  • X insieme discreto di stati
  • E insieme finito di eventi
  • f:X\times E\mapsto Xfunzione di transizione
  • \Gamma:X\mapsto 2^E \Gamma(x) restituisce l’insieme degli eventi abilitati in x
  • x_0 è lo stato iniziale
  • X_m\subseteq X insieme degli stati marcati

Rappresentazione grafica

Come ben noto gli automi possono essere rappresentati graficamente attraverso un grafo orientato:

  • i vertici rappresentano i possibili stati
  • gli archi rappresentano gli eventi che determinano l’evoluzione dello stato
Esempio di automa.

Esempio di automa.


Osservazioni

  • Se X è di cardinalità finito si parla di macchina a stati finiti o automa a stati finiti
  • La funzione \Gamma(\cdot) non è necessaria per poter definire un automa in quanto le stesse informazioni possono essere ricavate da f(\cdot,\cdot)
  • La definizione degli stati marcati dipende dal problema ed è lasciata al progettista

Estensione di f alle sequenze di eventi

Per convenienza la funzione di transizione f viene “estesa” anche alle stringhe di eventi

  • f(x\,,\varepsilon) = x
  • f(x\,,se)=f\bigl(f(x\,,s),e\bigr), con s\in E^\ast\,, e\in E

Linguaggio generato e linguaggio marcato da un automa

Dato un automa G = \bigl(X\,,E\,,f\,,\Gamma\,,x_0\,,X_m\bigr) è possibile definire i seguenti linguaggi

Linguaggio Generato da G

\mathcal{L}\bigl(G\bigr):=\bigl\{s\in E^\ast\ :\ f(x_0\,,s) è definita \bigr\}

Linguaggio Marcato da G

\mathcal{L}_m\bigl(G\bigr):=\bigl\{s\in \mathcal{L}\bigl(G\bigr)\ :\ f(x_0\,,s)\in X_m\bigr\}

Equivalenza tra automi

Due automi G_1 e G_2 si dicono Equivalenti se

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

e

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

Esempio di automi equivalenti

E = \bigl\{a\,,b\bigr\}

\mathcal{L}\bigl(G_1\bigr)=\mathcal{L}\bigl(G_1\bigr) = parole che iniziano con a
\mathcal{L}_m\bigl(G_1\bigr)=\mathcal{L}_m\bigl(G_1\bigr) = parole che finiscono con a

Automa G_1.

Automa G_1.

Automa G_2.

Automa G_2.


Esempio 1

X = \bigl\{x_0\,,x_1\,,x_2\bigr\}

E = \bigl\{a\,,b\,,c\bigr\}

X_m = \bigl\{x_1\,,x_2\bigr\}

f(x_0\,,a)=x_1,
f(x_0\,,b)=x_0,

\Gamma(x_0)=\bigl\{a\,,b\,,c\bigr\}
\Gamma(x_1)=\bigl\{a\,,b\bigr\}

\mathcal{L}\bigl(G\bigr)\bigl\{\varepsilon\,,a\,,b\,,c\,,aa\,,bb\,,cc\,,aab\,,\ldots\bigr\} = \bar{\mathcal{L}\bigl(G\bigr)}
\mathcal{L}_m,\bigl(G\bigr)\bigl\{a\,,c\,,aa\,,cc\,,aab\,,\ldots\bigr\} \neq\bar{\mathcal{L}_m\bigl(G\bigr)}

Automa esempio 1.

Automa esempio 1.


Proprietà dei linguaggi associati agli automi

Per i linguaggi associati agli automi (linguaggio generato e marcato) vale sempre

\mathcal{L}\bigl(G\bigr) = \overline{\mathcal{L}\bigl(G\bigr)} \Rightarrow il linguaggio generato è chiuso rispetto ai prefissi

\mathcal{L}_m\bigl(G\bigr)\subseteq \overline{\mathcal{L}_m\bigl(G\bigr)}\subseteq \mathcal{L}\bigl(G\bigr)

Quando si ha

\overline{\mathcal{L}_m\bigl(G\bigr)}\subset\mathcal{L}\bigl(G\bigr)

nell’automa G sono presenti dei Deadlock oppure dei Livelock

Esempio 2

In entrambi i casi si ha
\overline{\mathcal{L}_m\bigl(G\bigr)}\subset\mathcal{L }\bigl(G\bigr)

Deadlock.

Deadlock.

Livelock autonoma.

Livelock autonoma.


Automi bloccanti e non-bloccanti

In caso di deadlock e/o livelock l’automa si dice bloccante.

In particolare un automa è bloccante se

\overline{\mathcal{L}_m\bigl(G\bigr)}\subset\mathcal{L }\bigl(G\bigr)

altrimenti si dice non-bloccante se

\overline{\mathcal{L}_m\bigl(G\bigr)}=\mathcal{L }\bigl(G\bigr)

Esercizi proposti

Si considerino tre linguaggi L_1, L_2~ ed~ L_3. Mostrare che se L_2=L_1L_2\cup L_3 allora L_2=L^\ast_1L_3

Due linguaggi L_1 e L_2 si dicono non in conflitto se \overline{L_1\capL_2} = \overline{L_1}\cap\overline{L_2}

Fare un esempio di due linguaggi in conflitto.

Un linguaggio L\subseteq K si dice chiuso rispetto aK se L = \overline{L}\cap K

a) mostrare che se L_i è chiuso rispetto a K con i = 1\,,2 allora lo è anche L_1\cap L_2

b) mostrare che se L_a=\overline{L_a}, definendo L_{am} = L_a\cap K, allora L_{am} è chiuso rispetto a K

I materiali di supporto della lezione

Paragrafi 2.1 2.2 (fino al sottoparagrafo 2.2.3 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