Home

Federica EU

1/26

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

Chiusura rispetto ai prefissi e chiusura di Kleene
Concatenazione
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 X$ funzione 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.

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)$

$\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_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)}$