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 » 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