2
è non ambigua. Sul concetto di non ambiguità è basato un algoritmo
che decide l’univoca decifrabilità dei linguaggi regolari, quando questi
sono rappresentati da automi non ambigui [2]. Si tratta di automi in cui
non esistono due cammini distinti, che iniziano e finiscono negli stessi
stati e che definiscono la stessa parola. Parliamo dell’algoritmo di
Berstel e Perrin, che definisce un automa “ universale ”, l’automa
flower, dal quale è possibile decidere se il linguaggio definito
dall’automa iniziale è un codice. Head e Weber [11] e McCloskey [13]
mettono in evidenza il fatto che l’algoritmo basato sull’automa flower
esclude dagli input gli automi ambigui, i quali definiscono, anch’essi,
linguaggi regolari e quindi andrebbero considerati. In particolare, se si
volesse trasformare un automa ambiguo in non ambiguo questo
comporterebbe un incremento esponenziale nel numero degli stati.
Per tale motivo Head e Weber hanno disegnato un algoritmo efficiente
che decide l’univoca decifrabilità dei regolari verificando la single-
valuedness dei transducers.
L’algoritmo di McCloskey, oggetto del nostro lavoro, si concentra sullo
stesso obiettivo, ossia di eliminare l’inefficienza dovuta al passaggio
da ambiguo a non ambiguo, e si basa sul test di Sardinas e Patterson,
ma fornendo una generalizzazione del test ai linguaggi regolari.
L’algoritmo riceve in input un automa a stati finiti non deterministico
con -transizioni (eventualmente ambiguo) e si compone
fondamentalmente di quattro passi. Il primo passo consiste nel
verificare se la parola vuota (), appartiene al linguaggio definito
dall’automa in input. Questo viene realizzato attraverso una visita in
profondità del grafo che rappresenta l’automa, visitando solo gli archi
etichettati con . Il secondo passo, consiste nella costruzione di un
automa ristretto, ovvero un automa con un solo stato iniziale, un solo
3
stato finale e tale che lo stato finale non ha trasizioni in entrata
etichettata con , e nessuna transizione in uscita di qualsiasi tipo.
L’algoritmo è centrato sul concetto di automa ristretto, ma l’autore non
ha fornito un metodo sulla sua costruzione. Per tale motivo, il nostro
lavoro è consistito, anche, nel fornire un procedimento per la
costruzione dell’automa e nel dimostrare l’equivalenza tra -NFA e
automa ristretto. Il terzo passo prevede la costruzione di una variante
della definizione del prodotto di un automa, sull’automa ristretto
costruito al passo precedente. Infine l’ultimo passo consiste
nell’individuazione di un cammino, nell’automa costruito al passo
precedente, che dallo stato iniziale [q0, q0] porti allo stato finale [f, f]
passando per almeno uno stato semi-finale, ovvero uno stato [s, f] o
[f, s] con s f. L’esistenza di questo cammino permette di stabilire che
il linguaggio definito dall’automa iniziale non è unicamente decifrabile.
L’ultimo passo viene realizzato effettuando due visite in profondità. La
prima realizzata sull’automa del passo precedente, consiste nel creare
un insieme di stati semi-finali raggiungibili dallo stato iniziale. La
seconda effettuata sull’automa con le transizioni invertiti per creare un
insieme di stati semi-finali raggiungibili dallo stato finale. Se
l’intersezione tra i due insiemi è vuota, il linguaggio è un codice
altrimenti non lo è. Si dimostra che l’algoritmo è efficiente e richiede
tempo O(n2).
Per verificare, dal punto di vista pratico, la realizzabilità di tale
algoritmo nella sua complessità computazionale è stato realizzato un
progetto in Java 6 che ha seguito le linee guida di tale algoritmo. La
struttura dati “ automa ” rappresenta il concetto di automa ed eredita le
funzionalità della struttura dati “ grafo orientato ”. La classe
ConvertNFAToRestrictedAutomaton effettua la conversione
4
dell’automa fornito in input in automa ristretto, mentre la classe
ProductAutomaton costruisce l’automa prodotto definito nel terzo
passo dell’algoritmo. La classe Dfs, invece, contiene diversi metodi per
la realizzazione delle diverse versioni della visita in profondità di un
grafo, utilizzate nei diversi punti dell’algoritmo.
È stata inoltre prevista una seconda fonte di input, l’espressione
regolare, con l’ausilio del software JFlap, sviluppato per effettuare
esperimenti in ambito di linguaggi formali. In particolare, JFlap
consente di trasformare un’espressione regolare in un automa a stati
finiti deterministico utilizzando il relativo teorema. Le classi
ConvertREToNFAutomaton e ConvertFSAToNFAutomaton effettuano
le conversioni tra le strutture dati di JFlap e quelle realizzate nel nostro
progetto. A completamento del progetto si è prodotto un’interfaccia
grafica che consente all’utente di disegnare un automa o inserire
un’espressione regolare attraverso l’ausilio delle interfacce grafiche di
JFlap, e di visualizzare l’esito dell’esecuzione dell’algoritmo sull’input
definito dall’utente stesso.
Capitolo 1 Preliminari
5
CAPITOLO 1
Preliminari
In questo primo capitolo diamo una breve panoramica delle nozioni
base utilizzate, con particolare riferimento alle definizioni di alfabeto,
monoide, parola e linguaggio tratte da [2].
1.1 Monoide
Un alfabeto è un insieme finito i cui elementi sono detti lettere o
simboli.
Capitolo 1 Preliminari
6
Un monoide M è un insieme dotato di un’operazione associativa
binaria e di un elemento neutro. L’operazione è denotata con • ,
talvolta omesso se chiaro dal contesto. L’elemento neutro è unico ed è
denotato da M o semplicemente da .
Siano X, Y ⊂ M, definiamo
XY = { xy | x ∈ X, y ∈ Y }.
Un sottomonoide di M è un sottoinsieme N che è stabile con
l’operazione e contiene l’elemento neutro di M, ossia
NN ⊂ N, (1.1.1)
M ∈ N. (1.1.2)
Si noti che un sottoinsieme N di M che soddisfa la (1.1.1) non sempre
verifica M = N e quindi può capitare che N sia un monoide senza
essere sottomonoide di M.
Un morfismo da un monoide M in un monoide N è una funzione
: M N
tale che per ogni m, m’ ∈ M, si ha
(mm’) = (m) (m’),
e ancora
(M) = N.
Un idempotente di un monoide è un elemento e di M tale che
e = e2.
Per ogni idempotente e di un monoide M, l’insieme
M(e) = eMe
Capitolo 1 Preliminari
7
è un monoide contenuto in M.
Ricordiamo anche che un semigruppo è un insieme dotato di
un’operazione associativa ma senza il requisito dell’esistenza
dell’elemento neutro. Le nozioni di sottosemigruppo e morfismo di
semigruppo sono definite nello stesso modo delle corrispondenti
nozioni per monoidi.
Sia M un monoide. Per x, y ∈ M, definiamo
x -1y = { z ∈ M | xz = y} e xy -1 = { z ∈ M | x = zy}.
Per sottoinsiemi X, Y di M, questa notazione è estesa a
X -1Y = Ux∈X Uy∈Y x -1y e XY -1 = Ux∈X Uy∈Y xy -1 (1.1.3)
Le seguenti identità sono valide per sottoinsiemi X, Y, Z di M:
(XY) -1Z = Y -1(X -1 Z) e X -1(YZ -1) = (X -1Y)Z -1.
Dato un sottoinsieme X di un monoide M, definiamo
F(X) = M -1XM -1
come l’insieme dei fattori degli elementi in X. Abbiamo
F(X) = { m ∈ M | ∃ u, v ∈ M: umv ∈ X }.
Solitamente usiamo la notazione F(X) per denotare il complemento di
F(X) in M,
F(X) = M – F(X).
Capitolo 1 Preliminari
8
1.2 Parole
Sia un alfabeto. Una parola w sull’alfabeto è una sequenza finita
di elementi di
w = ( a1, a2, ……, an ), ai ∈
L’insieme di tutte le parole sull’alfabeto è denotato da * ed è dotato
di un’operazione associativa definita dalla concatenazione di due
sequenze
( a1, a2, ……, an )( b1, b2, ……, bm ) = ( a1, a2, ……, an, b1, b2, ……, bm )
Questa operazione è associativa e permette di scrivere
w = a1a2……an
invece di w = ( a1, a2, ……, an ), identificando ciascun elemento a ∈
con la sequenza (a).
La sequenza vuota è chiamata parola vuota, è denotata da e
rappresenta l’elemento neutro. Così * è dotato della struttura di un
monoide ed è chiamato monoide libero su .
L’insieme delle parole non vuote su è rappresentato con + e quindi
avremo
+ = * / .
La lunghezza |w| della parola w = a1a2…… an è il numero n di lettere
in w. Chiaramente, | | = 0.
La funzione w |w| è un morfismo da * nel monoide additivo N degli
interi non negativi. Per n 0, usiamo la notazione
(n) = { w ∈ * | |w| n-1 }
ed inoltre
[n] = { w ∈ * | |w| n }.
Capitolo 1 Preliminari
9
In particolare, (0) = ∅ e [0] = { }.
Una parola w ∈ * è un fattore di una parola x ∈ * se esiste u, v ∈
* tale che x = uwv.
La relazione “ è un fattore di ”, è un ordine parziale su *. Un fattore w
di x è proprio se w x.
Una parola w è un prefisso di una parola x ∈ * se c’è una parola u ∈
* tale che x = wu. Il fattore w è chiamato proprio se w x. La
relazione “ è un prefisso di ”, è ancora un ordine parziale su * che
prende il nome di ordinamento prefisso.
Scriviamo w x quando w è prefisso di x e w < x ogni qualvolta w è
prefisso proprio di x.
Questo ordine gode di una proprietà fondamentale:
Proposizione 1.1:
Siano w, w’, x ∈ *. Se
w x, w’ x,
allora w e w’ sono confrontabili, cioè
(a) w w’ o (b) w’ w.
w w’’
x
w’ w’’’ w’ w’’’
(a) (b)
x x
Figura 1.1
Capitolo 1 Preliminari
10
In altre parole, se vw = v’w’, allora esiste s ∈ * tale che v = v’s (ed
inoltre sw = w’) oppure esiste t ∈ * tale che v’ = vt (ed allora w = tw’).
Un insieme P ⊂ * è chiamato chiuso per prefissi se contiene i
prefissi dei suoi elementi: uv ∈ P u ∈ P.
Similarmente possiamo introdurre la nozione di suffisso.
Una parola w è un suffisso di una parola x ∈ * se c’è una parola v ∈
* tale che x = vw. Il suffisso w sarà proprio se w x.
Un insieme S ⊂ * è chiamato chiuso per suffisso se contiene i suffissi
dei suoi elementi: uv ∈ S v ∈ S.
La potenza n-esima di una parola w è data dalla concatenazione
della parola stessa per n volte:
se n = 0
w n-1w altrimenti
Introduciamo ora una nozione chiave nella teoria dei codici.
Una fattorizzazione di una parola w ∈ * è una sequenza { u1, u2,
……, un } di n 0 parole di * tale che
w = u1u2……un.
Per un sottoinsieme X di *, denotiamo con X*, il sottomonoide
generato da X,
X* = { x1x2…… xn | n 0, xi ∈ X }
Un insieme X che genera un sottomonoide libero M di * è chiamato
la base di M.
w n =
Ricevi informazioni sui nostri servizi, sulle offerte e non perdere news e consigli su università e lavoro.
