Alfabeti, Stringhe e Linguaggi
Def: un insieme è una collezione non ordinata di oggetti o
elementi
Gli insiemi sono scritti tra { }.
Gli elementi sono inseriti tra le parentesi
Def:
Per ogni insieme S, “w є S” indica che w è un elemento di S
Nota: Notazione di insiemi per specificare un’insieme
A = { x | x є R, f(x) = 0}
R è insieme dei numeri reali, f è una qualche funzione
Insiemi
Es:
{a, b, c} ha elementi a, b, c.
{a, b, c} e {b, c, b, a, a} sono lo stesso insieme.
Ordine e ridondanza non contano.
{a} ha elemento a.
{a} ed a sono coSe diverse.
{a} è l’insieme che contiene solo elemento a.
L’insieme degli interi è
Z = {. . . ,.-2,-.1, 0, 1, 2, . . .}.
L’insieme degli interi non negativi è
Z+ = {0, 1, 2, 3, . . .}.
Insiemi
Es:
L’insieme dei numeri pari è
{0, 2, 4, 6, 8, 10, 12, . . .} = { 2n | n = 0, 1, 2, . . . }.
L’insieme dei pari positivi è
{2, 4, 6, 8, 10, 12, . . .} = { 2n | n = 1, 2, 3, . . . }.
L’insieme dei numeri dispari è
{1, 3, 5, 7, 9, 11, 13, . . .} = { 2n+1 | n = 0, 1, 2, . . . }.
Es: Se A = { 2n | n = 0, 1, 2, . . . },
allora 4 є A, ma 5 non in A.
Alfabeti
Un alfabeto è un insieme finito di elementi fondamentali
(chiamati lettere o simboli)
Es:
L’alfabeto delle lettere romane minuscole è
S={ a, b, c, . . . , z }.
Es:
L’alfabeto delle cifre arabe è
S={ 0, 1, 2, . . . , 9 }.
stringa
Def: Una stringa su un alfabeto è una sequenza finita di
simboli dell’ alfabeto.
Es:
cat, food, c, babbz sono stringhe sull’ alfabeto
A={a, b, c, . . . , z}.
0131 è una stringa sull’ alfabeto B={0, 1, 2, . . . , 9}.
Lunghezza di una stringa
Def: per ogni stringa s, la lunghezza di s è il numero di
simboli in s.
La lunghezza di s è denotata con lunghezza(s) o |s|.
Es:
lunghezza(mom) = |mom| = 3.
Def: la stringa vuota e è la stringa contenente nessun
simbolo, |e| = 0.
Kleene Star
Def: Dato alfabeto S, sia S* l’insieme di tutte le possibili
stringhe su S.
Es: S={a, b}, allora
S* = { e, a, b, aa, ab, ba, bb, aaa, aab, aba, abb, . . . }.
Concatenazione
Def: Date due stringhe u e v, la concatenazione di
u e v è la stringa uv.
Es:
u = abb e v = ab, allora uv = abbab e vu = ababb.
u = e e v = ab, allora uv = ab.
u = bb e v = e, allora uv = bb.
u = e e v = e, allora uv = e; cioè ee=e
Def: per stringa w, definiamo wn per n > 0 induttivamente:
w0 = e;
wn+1 = wnw per ogni n > 0.
Es: w = cat, allora
w0 = e,
w1 = cat,
w2 = catcat,
w3 = catcatcat,
...
Es:Dato simbolo a
a3 = aaa
a0 = e
Sottostringa
Def: Data stringa s, una sottostringa di s è una
qualsiasi parte di simboli consecutivi della stringa s.
cioè, w è una sottostringa di s se esistono stringhe
x e y (eventualmente vuote) tali che s = xwy.
Es:
Stringa 472 ha sottostringhe e, 4, 7, 2, 47, 72, 472.
42 non è sottostringa di 472.
Linguaggi
Def: Un Linguaggio formale (Linguaggio) è un insieme di
stringhe su un alfabeto.
Es:
Linguaggi per computer, quali C o C++ o Java, sono
linguaggi permali con alfabeto
A = {a, b, . . . , z, A, B, . . . , Z, ,0, 1, 2, . . . , 9,
>, <, =, +, -, *, /, (, ), ., ,, &, !, %, |, ’, ",
:, ;,ˆ, {, }, @, #, \, ?}.
Le regole della sintassi definiscono le regole del linguaggio.
L’insieme di nomi validi di variabili in C++ è un Linguaggio
formale .
Esempi di Linguaggi
1. alfabeto A={x}. Linguaggio
L = { e, x, xx, xxx, xxxx, . . . }= { xn | n = 0, 1, 2, 3 . . . }
Nota: x0 = e, quindi stringa vuota in L
2. alfabeto A={x}. Linguaggio
L = { x, xxx, xxxxx, xxxxxxx, . . . }={ x2n+1 | n = 0, 1, 2, 3, . . . }
3. alfabeto A={0, 1, 2, . . . , 9}. Linguaggio
L = { qualsiasi stringa che non inizia con “0”}
= { e, 1, 2, 3, . . . , 9, 10, 11, . . . }
Esempi di Linguaggi
Es: Sia A={a, b}, definiamo Linguaggio L formato
da tutte le stringhe che iniziano con a seguita da 0 o più b;
Cioè L = { a, ab, abb, abbb, . . . }= { abn | n = 0, 1, 2, . . . }.
Def: l’ insieme vuoto f è l’ insieme contenente nessun
elemento.
Nota:
e non in f
f non è uguale a {e}
poichè f non ha elementi.
Insiemi: Relazioni ed Operazioni
Def: Se S e T sono insiemi, allora
S T (S è sottoinsieme di T) se w  S implica w  T.
Cioè ogni elemento di S è anche un elemento T.
Es:
S = { ab, ba }, T = { ab, ba, aaa } allora S  T ma T

 T e T
S.
S = { ba, ab } e T = { aa, ba } allora S
S.
Insiemi uguali
Def: insiemi S e T, sono uguali (S = T), Se S T e T S.
Es:
Sia S = { ab, ba } e T = { ba, ab }. allora S
quindi S = T.
Sia S = { ab, ba } e T = { ba, ab, aaa },
allora S  T, ma T
Quindi S
 T.
 S.
T e T
S.
Unione
Def: Dati due insiemi S e T, la loro unione è
S U T = {w | w
 S o w T }
S U T contiene tutti gli elementi in S oppure in T (o in
entrambi).
Es:
S = { ab, bb } e T = { aa, bb, a }, allora S U T = { ab, bb, aa, a }.
S = { a, ba } e T = f, allora S U T = S.
S = { a, ba } e T = { e }, allora S U T= { e, a, ba }.
Intersezione
Def: Dati due insiemi S e T, la loro Intersezione è
S ∩ T = {w | w S e w  T },
S ∩ T consiste degli elementi sia di S che di T.
Def: insiemi S e T sono disgiunti se
S ∩ T = f.
Es:
Sia S = { ab, bb } e T = { aa, bb, a }, allora S ∩ T = { bb }.
Sia S = { ab, bb } e T = { aa, ba, a }, allora S ∩ T = f, quindi
S e T sono disgiunti
Sottrazione
Def: Dati 2 insiemi S e T, S -T = {w | w
S, w T }.
Es:
Sia S = { a, b, bb, bbb } e T = { a, bb, bab }
allora S -T = { b, bbb }.
Sia S = { ab, ba } e T = { ab, ba } allora S -T = f.
Complemento
Def: Dato insieme S, il suo complemento è
C(S)= {w | w
 S }.
C(S) è l’ insieme di tutti gli elementi considerati che non
sono in S.
Es:
Sia S l’ insieme delle stringhe su alfabeto {a, b} che iniziano
con il simbolo b.
allora C(S) è insieme stringhe su {a, b} che non iniziano con b,
C(S) NON è l’ insieme stringhe su {a, b} che iniziano con a
(es. stringa vuota e)
Concatenazione
Def: Dati 2 insiemi S e T di stringhe, la concatenazione (o
prodotto) di S e T è
ST = { uv | u  S, v T }.
Nota:
ST è l’ insieme di stringhe che possono essere divise in 2
parti: la prima parte è in S e la seconda parte è in T.
Es:
S = { a, aa } e T = { e, a, ba }, allora
ST = { a, aa, aba, aaa, aaba }, TS = { a, aa, aaa, baa, baaa }.
 ST, ma aba TS.
ST TS
aba
Cardinalità
Def: La cardinalità |S| di S è il numero di elementi in S.
Es:
Sia S = { ab, bb } e T = { an | n > 1 }, allora |S| = 2 e |T| = ∞.
Se S = f , allora |S| = 0.
Insiemi Finiti ed Infiniti
Def:
Un insieme S è finito se |S| < ∞.
Se S non è finito, allora S è infinito.
Es:
Sia S = { ab, bb }, allora S è finito.
Sia T = { an | n > 1 }. allora T è infinito.
Fatto: Se S e T sono disgiunti (cioè S ∩ T = vuoto.),
allora
|S U T| = |S|+|T|.
Fatto: Se S e T sono tali che |S ∩ T| < ∞, allora
|S U T| = |S|+|T| - |S ∩ T|.
Sequenze e tuple
Def: sequenza di oggetti è una lista di questi oggetti in
qualche ordine.
ordine e ridondanza sono importanti in una sequenza (non in
un insieme).
Def: sequenze finite sono dette tuple.
A k-tupla ha k elementi nella sequenza.
Es:
(4, 2, 7) è a 3-tupla o tripla
(9, 23) è a 2-tupla o coppia.
Prodotto Cartesiano
Def: Dati due insiemi A e B, il prodotto Cartesiano è l’
insieme di coppie
A × B = { (x, y) | x A, y B }.
 
Es: Sia A = { a, ba, bb } e B = { e, ba }, allora
A × B = { (a, e), (a, ba), (ba, e), (ba, ba), (bb, e), (bb, ba) }.
per Es, la coppia (a, ba) in A × B.
B × A = { (e, a), (e, ba), (e, bb), (ba, a), (ba, ba), (ba, bb) }.
 B × A, ma
 A × B.
Nota (ba, a)
Quindi B × A
(ba, a) non in A × B,
Nota che la Concatenazione
A B = { a, aba, ba, baba, bb, bbba }

A × B.
Nota: |A × B| = |A| |B|. Perchè?
Nota: Possiamo anche definire prodotto cartesiano di più
di 2 insiemi.
Def: prodotto cartesiano di k insiemi
A1,A2, . . . , Ak è l’ insieme di k-tuple
A1 × A2 × … ×Ak
= { (x1, x2, . . . , xk) | xi
A per i = 1, 2, . . . , k }
i
Es:
Sia
A1 = { ab, ba, bbb },
A2 = { a, bb },
A3 = { ab, b }.
allora
A1 × A2 × A3 = { (ab, a, ab), (ab, a, b), (ab, bb, ab),
(ab, bb, b), (ba, a, ab), (ba, a, b), (ba, bb, ab), (ba, bb, b),
(bbb, a, ab), (bbb, a, b), (bbb, bb, ab), (bbb, bb, b) }.
Insieme potenza
Def: per ogni insieme S, l’ insieme potenza
P(S) = {A | A in S }.
L’ insieme potenza
sottoinsiemi di S.
P(S) è
di S è l’ insieme di tutti possibili
Es: Se S = { a, bb }, allora P(S) = { f, {a}, {bb}, {a, bb} }.
Fatto: Se|S| < ∞, allora |P(S)| = 2|S|
Cioè , ci sono 2|S| differenti sottoinsiemi di S. Perchè?
Chiusura
Def: Dato insieme S di stringhe, sia
S0 = { e }, e
Sk = {w1 w2 … wk | wi in S, i = 1, 2, . . . , k }=
=S . S . … . S, k volte,
per k > 1.
Nota:
Sk è insieme di stringhe ottenute concatenando k stringhe
di S, con possibili ripetizioni.
Nota che S1 = S.
Es: Se S = {a, bb}, allora
S0 = {e},
S1 = {a, bb}, S2 = {aa, abb, bba, bbbb},
S3 = {aaa, aabb, abba, abbbb, bbaa, bbabb, bbbba, bbbbbb}.
Chiusura Kleene Star
Def: la Chiusura (Kleene star) di un insieme di stringhe S è
S*= S0 U S1 U S2 U S3 U … .
Nota:
S* è l’ insieme di tutte le stringhe ottenute concatenando
zero o più stringhe di S, dove possiamo usare la stessa
stringa più volte.
S.*= {w1 w2 … wk | k > 0 e wi in S per tutti i = 1, 2, . . . , k },
Dove w1 w2 … wk per k = 0 è la stringa vuota.
Es: Se S = { ba, a }, allora
S* = { e, a, aa, ba, aaa, aba, baa, aaaa, aaba, . . . }.
Se w in S., puo’ bb essere una sottostringa di w?
Es: Se A={ a, b }, allora
A* = { e, a, b, aa, ab, ba, bb, aaa, aab, aba, . . . },
tutte possibili stringhe su alfabeto A.
Es: Se S = f, allora S* = { e }.
Es: Se S = { e }, allora S* = { e }.
S**
S** è (S*)*, l'insieme di stringhe formate concatenando
stringhe di S*
Fatto: S** = S* per ogni insieme S di stringhe.
S+
Def: Se S è qualche insieme di stringhe, allora
S+ è l'insieme di tutte le stringhe ottenute concatenando
una o più stringhe di S.
Es: Se S={ x }, allora S+ = { x, xx, xxx, . . . }.
Inverso di stringhe
Def: per ogni stringa w, l'inverso di w, scritto reverse(w)
o wR, è la stessa stringa di simboli scritta in ordine
inverso .
Se w = w1 w2 … wn, dove ogni wi è un simbolo, allora
wR = wn wn-1 … w1.
Es: (cat)R = tac e eR = e.

per xxx in L1={xn | n = 1, 2, 3, . . .}, reverse(xxx) = xxx L1
Sia L3 l'insieme di stringhe su {0, 1, 2, . . . , 9} tali che il
primo simbolo non è 0.
Nota che 10 in L3, ma (10)R = 01 non in L3.
quindi , L3 è non chiuso per l’inverso.
Grafi
Def: Un grafo orientato G=(V,E) è composto da un insieme
V di nodi (o vertici) ed un insieme E di archi.
In grafo G che contiene nodi i e j, la coppia (i, j) in E
rappresenta arco da nodo i a nodo j.
Es per il grafo disegnato,
V = {1, 2, 3},
E = { (1, 2), (1, 3), (2, 3), (3, 2), (3, 3) },
G = ({1, 2, 3}, { (1, 2), (1, 3), (2, 3), (3, 2), (3, 3) } ).
AUTOMI
Introduciamo ora un modello semplice di calcolatore avente
una quantità finita di memoria
E’ noto come macchina a stati finiti o automa finito .
Idea di base del funzionamento:
•Input= stringa su un alfabeto
•Legge i simboli di w da sinistra a destra.
•Dopo aver letto l’ultimo simbolo, l’automa indica se accetta
o rifiuta la stringa
Utili per progettare compilatori.
Automa finito deterministico (DFA)
Es: DFA con alfabeto A={a, b}:
q1, q2, q3 soni gli stati.
q1 è lo stato start (ha freccia entrante da esterno)
q2 è uno stato accetta (disegnato con doppio cerchio)
archi dicono come muoversi quando l’automa si trova in uno
stato e simbolo di A è letto .
Dopo aver letto l’ultimo simbolo:
Se DFA è in uno stato accetta, allora stringa è accettata,
altrimenti è rifiutata .
Nell’esempio:
abaa è accettata
aba è rifiutata
e è rifiutata
Def di DFA formale
Def: A automa finito deterministico (DFA) è 5-tupla
M = (Q,A, f, q1, F),
dove
1. Q è insieme finito di stati.
2. A è alfabeto, e il DFA processa stringhe su A.
3. f : Q × A -> Q è la funzione di transizione.
4. q1 Q è lo stato start.
5. F (sottoinsieme di Q) è l'insieme di stati accetta (o
stati finali ).

Nota: DFA chiamato anche semplicemente automa finito
(FA).
Funzione di transizione di DFA
funzione di transizione f : Q × A -> Q :
per ogni stato e per ogni simbolo di input,
la funzione f dice in quale stato spostarsi.
Cioè, f(r, a) è lo stato che il DFA occupa quando è in stato
r e legge a , per ogni coppia formata da uno stato r in Q ed
un simbolo a in A.
Esiste esattamente un arco uscente da r con label a
quindi la macchina è deterministica.
Es di DFA
M = (Q,A, f, q1, F) con
Q = {q1, q2, q3}
A={a, b}
f è descritta da
q1 è lo stato start
F = {q2}.
Come un DFA Computa
• DFA riceve in input stringhe di simboli di alfabeto A.
• DFA inizia in stato start.
• DFA legge la stringa un simbolo alla volta, partendo da
sinistra
• il simboli letto determina la sequenza di stati visitati.
• Processo termina dopo che l’ultimo simbolo input è stato
letto .
• Dopo letto intera stringa input:
Se DFA termina in stato accetta, allora stringa è
accettata
altrimenti , è rifiutata .
Definizione formale
Sia M = (Q,A, f, q0, F) un DFA.
Considera stringa w = w1w2 · · ·wn su A., doveogni wi in A.
M accetta w se esiste sequenza di stati r0, r1, . . . , rn in Q
tali che
1. r0 = q0 (primo stato della sequenza è quello iniziale)
2. rn in F (ultimo stato in sequenza è uno stato accetta)
3. f(ri-1, wi) = ri , per ogni i = 1, 2, . . . , n (sequenza di stati
corrisponde a transizioni valide per la stringa w).
Linguaggio della Machina
Def: Se A è l'insieme di tutte le stringhe che la machina M
accetta, allora si dice che
•A è il Linguaggio della machina M, e
•M riconosce (o accetta) A.
Scriviamo anche L(M) = A.
Def: Un Linguaggio è regolare se è riconosciuto da qualche
DFA.
Es: Si consideri il seguente DFA M1 con alfabeto A={0, 1} :
010110 è accettata , ma 0101 è rifiutata .
L(M1) è il Linguaggio di stringhe su A in cui il numero totale di
1 è dispari.
Esercizio: dare DFA che riconosce il Linguaggio di stringhe su
A con numero pari di 1’s
Es: DFA M2 con alfabeto A={0, 1} :
Nota:
L(M2) è Linguaggio su A che ha lunghezza 1, cioè
L(M2) = {w in A | |w| = 1}
Si ricordi che C(L(M2)), il complemento di L(M2), è l'insieme
di stringhe su A che non sono in L(M2).
Domanda: DFA che riconosce C(L(M2))?
Es: Si consideri il seguente DFA M3 con alfabeto A={0, 1}
L(M3) è il Linguaggio su A che non ha lunghezza 1,
Più di uno stato accetta.
Stato start anche stato accetta.
In generale, DFA accetta e sse lo stato start è anche
stato accetta.
DFA per Complemento
In generale, Dati DFA M per Linguaggio L,
possiamo costruire DFA M’ per C(A) da M
rendendo tutti gli stati accetta in M in stato non-accept in M’,
rendendo tutti stati non-accetta in M in stati accetta in M’,
Più formalmente,
Se Linguaggio L su alfabeto A ha un DFA
M = (Q, A, f, q1, F ).
allora, DFA per il complemento di L è
M = (Q, A, f, q1, Q- F ).
Esercizio: Perchè funziona?
Es: Si consideri il seguente DFA M4 con alfabeto A={a, b} :
L(M4) è il Linguaggio di stringhe su A che terminano con
bb, cioè
L(M4) = {w in A | w = sbb per qualche stringa s}
Es: Si consideri il seguente DFA M5 con alfabeto A={a, b}
L(M5) = {w | w = saa o w = sbb per qualche stringa s}.
Si consideri il seguente DFA M6 con alfabeto A={a,b}
Accetta tutte le possibili stringhe su A, cioè
L(M6) = A*
In generale, ogni DFA in cui tutti stati sono stato
accetta riconosce il linguaggio A*
Si consideri il seguente DFA M6 con alfabeto A={a,b}
DFA non accetta stringhe su A, cioè
L(M7) = f
In generale, un DFA può non avere stati accetta
Es: Si consideri il seguente DFA M8 con alfabeto A={a, b} :
•Ogni a muove verso destra o sinistra.
• Ogni b muove verso l’alto o il basso
•DFA riconosce il Linguaggio di stringhe su A con
numero pari di a e numero pari di b.
Operazioni regolari
Siano A e B Linguaggi.
Unione: AU B = {w | w  A o w  B }.
Concatenazione: AB = { vw | v  A,w  B }.
Kleene star: A*= {w1 w2 · · · wk | k > 0 e ogni wi  A}.
• Una collezione S di oggetti è chiusa per un operazione f se
applicando f a membri di S, f restituisce un oggetto in S.
ad es. N = {0, 1, 2, . . .} è chiuso per addizione ma non per
sottrazione
•Abbiamo visto che dati DFA M1 per Linguaggio L, possiamo
costruire DFA M2 per Linguaggio complemento L’:
Rendi tutti stato accetta in M1 in non-stato accetta in M2.
Rendi tutti stati non-accetta in M1 in stati accetta in M2.
quindi , l'insieme di Linguaggi regolari è chiuso per
complemento.
•cioè se L è regolare, allora C(L) è regolare.
Linguaggi regolari chiusi per l’ unione
Teorema
La classe dei linguaggi regolari è chiusa per l’unione.
cioè, se L1 e L2 sono linguaggi regolari , allora lo è anche
L1 U L2.
Dim Idea:
L1 ha DFA M1.
L2 ha DFA M2.
w in L1 UL2 sse w è accettata da M1 oppure M2.
Serve DFA M3 che accetta una stringa w sse w è accettata
da M1 o M2.
Si costruisca M3 tale da tener traccia di dove l’ input sarebbe
se fosse contemporaneamente in input a M1 e M2.
accetta stringa sse M1 oppure M2 accetta.
Siano L1 e L2 definiti su the stesso alfabeto A.
DFA M1 riconosce L1, dove M1 = (Q1,A, f1, q1, F1).
DFA M2 riconosce L2, dove M2 = (Q2,A, f2, q2, F2).
Sia DFA M3 = (Q3,A, f3, q3, F3) :
•Q3 = Q1 × Q2 = { (x, y) | x in Q1, y in Q2 }.
• alfabeto di M3 è A.
•M3 ha funzione di transizione f3 : Q3 × A -> Q3 t.c. per
x in Q1, y in Q2, e a in A,
f3( (x, y),a ) = ( f1(x, a), f2(y,a ) ) .
•Lo stato start di M3 è q3 = (q1, q2) in Q3.
•L’ insieme di stati accept di M3 è
F3 = { (x, y) in Q1 × Q2 | x in F1 o y in F2 }
Poichè Q3 = Q1 × Q2,
numero di stati in M3 è |Q3| = |Q1| · |Q2|.
Quindi, |Q3| è finito poichè |Q1| e |Q2| sono finiti.
Es: Si considerino i seguenti DFA e linguaggi su A={a, b} :
DFA M1 riconosce linguaggio A1 = L(M1)
DFA M2 riconosce linguaggio A2 = L(M2)
DFA M1 per A1
DFA M2 per A2
Vogliamo DFA per l’unione di A1 e A2.
I linguaggi regolari sono chiusi per l’intersezione
Teorema
La classe dei linguaggi regolari è chiusa per l’intersezione.
cioè, se A1 e A2 sono linguaggi regolari, allora lo è A1  A2.
Dim. Idea:
• A1 ha DFA M1.
• A2 ha DFA M2.
• w in A1  A2 sse w è accettato sia da M1 che da M2.
•Si vuole DFA M3 che accetta w sse w è accettata da M1 e M2.
•Costruiamo M3 che contemporaneamente mantiene traccia
dello stato in cui si troverebbero sia M1 che M2.
• Accetta stringa sse sia M1 che M2 accettano
I linguaggi regolari sono chiusi per Concatenazione
Teorema
Classe dei I linguaggi regolari è chiusa per la concatenazione.
cioè, se A1 e A2 sono linguaggi regolari, allora lo è A1 A2.
NOTA:
E’ possibile (ma laborioso) costruire un DFA per
A1 A2 dati i DFA per A1 e A2.
Introduciamo invece un nuovo tipo di macchina
Automi finiti non deterministici
In DFA, lo stato successivo occupato in corrispondenza di un
dato input è unicamente determinato
Quindi le macchine sono sono deterministiche.
La funzione di transizione in un DFA è definita come
f : Q × A -> Q.
Restituisce sempre un singolo stato
Nondeterminismo
Automi finiti non deterministici (NFA) permettono più
scelte per il prossimo stato per un dato input.
per uno stato q e simbolo a in a, NFA può avere
più edges uscenti da q labellati con lo stesso simbolo
può prendere e-edge senza leggere simboli da input.
Es.: NFA N1 con alfabeto A={0, 1}.
Se NFA è in stato con più scelte, (Es.., in stato q1 e prossimo
input è 1) la macchina si divide in più copie di se stessa.
Ogni copia continua con computazione indipendentemente dalle
altre.
NFA può essere in un insieme di stati, invece di un singolo
stato.
NFA segue ogni possibile computazione in parallelo:
se una copia porta a uno stato accept alla fine dell’input, NFA
accetta la stringa;
se, al temine dell’input, nessun cammino si trova in uno stato
accept allora NFA non accetta la stringa.
Se in stato con e-transition, senza leggere input,
NFA si divide in più copie, ognuna segue una transizione,
ogni copia continua indipendentemente da altre copie,
NFA segue ogni possibile cammino in parallelo.
NFA continua non deterministicamente come prima.
Su input 010110 ?
NFA N accetta stringhe e, a, aa, baa, baba, . . . .
NFA N non accetta stringhe b, ba, bb, . . . .
Def.di NFA
Def.: Per alfabeto A, sia Ae ottenuto da A aggiungendo e
Def.: A NFA è 5-tupla (Q,A, f, q0, F), con
1. Q insieme di stati
2. A alfabeto
3. f : Q × Ae->P(Q) funzione di transizione
4. q0 in Q è stato start
5. F insieme di stati accept.
Nota: La differenza tra DFA e NFA è nella funzione di
transizione f:
ammette mosse tipo e
Restituisce insieme di stati invece di un solo stato.
Computazione di NFA
Sia N = (Q,A, f, q0, F) un NFA e w una stringa su A
allora N accetta w se
w = y1 y2 · · · ym, dove ogni yi in Ae, e
esiste sequenza di stati r0, r1, . . . , rm in Q t.c.
1. r0 = q0
2. ri+1 in f(ri, yi+1) per ogni i = 0, 1, 2, . . . , m - 1
3. rm in F
Def.: insieme di stringhe accettate da NFA N è
il linguaggio riconosciuto da N ed è denotato con L(N).
Remark: ogni DFA è anche un NFA.
Equivalence di DFAs e NFAs
Def.: due macchine sono equivalenti se riconoscono lo stesso
linguaggio.
Teorema
Ogni NFA N ha un equivalente DFA M.
cioè, se N è un NFA, allora esiste DFA M t.c. L(M) = L(N).
NFA Regolari
Corollario
linguaggio L è regolare sse esiste NFA che riconosce A.
Dim.
Se L è regolare, allora esiste DFA
ma ogni DFA è anche un NFA, quindi esiste NFA per A.
Da Teorema precedente, ogni NFA ha equivalente DFA.
Quindi se esiste NFA allora esiste DFA per L
DIMOSTRAZIONE CHIUSURA CONCATENAZIONE
AB = { vw | v in A, w in B }.
Teorema
La classe dei linguaggi regolari è chiusa per la
concatenazione.
Dim Idea: NFA N per A1 A2 :
L1 linguaggio riconosciuto da NFA N1 = (Q1,A, f1, q1, F1).
L2 linguaggio riconosciuto da NFA N2 = (Q2,A, f2, q2, F2).
NFA N = (Q,A, d, q1, F2) per L1L2 :
Q = Q1 U Q2
Stato start q1, stesso di N1.
Stati finali F2, stessi di N2.
Funzione di transizione:
Si può estendere alla Kleene star:
A* = { x1 x2 · · · xk | k > 0, xi in L}.
Teorema
La classe dei linguaggi regolari è chiusa per l’operazione
Kleene-star.
DIM IDEA. Se N1 riconosce L. Costruiamo N da N1 in cui ogni
stato finale è collegato da e-transizione allo stato iniziale
Espressioni regolari
Espressioni regolari descrivono i linguaggi regolari
Sia A={0, 1}. Per brevità nelle espressioni regolari:
0 indica {0}, 1 indica {1}
Es: 0 U 1 indica {0} U {1}, cioè {0, 1}.
Es: (0 U 1)0* è {0, 1} . {0}*. (dove {0}*. = {e, 0, 00, 000, . . .}.)
quindi, {0, 1} . {0}* è insieme di stringhe che iniziano con 0
oppure 1 e continuano con degli 0 (anche nessuno)
Es. (0 U 1)* è insieme di tutte stringhe su A={0, 1}.
Gerarchia di operazioni in espressioni regolari
In aritmetica, moltiplicazione ha precedenza su addizione.
2+3×4 = 14.
Parentesi cambiano ordine usuale: (2+3) ×4 = 20.
Ordine di precedenza per operazioni regolari
1. Kleene star
2. concatenazione
3. unione
Parentesi cambiano ordine usuale
Gerarchia di operazioni in espressioni regolari
Ordine di precedenza per operazioni regolari
1. Kleene star
2. concatenazione
3. unione
Es: 00 U 101* linguaggio formato da stringa 00 e da
stringhe inizianti con 10 seguita da zero o più 1.
Es: 0(0 U 101)* ?
0101001010 in linguaggio?
Definizione formale di espressione regolare
Def: Alfabeto A. R è espressione regolare se R =
1. a , per qualche a in A,
2. e
3. f
4. R1 U R2,
5. R1 R2,
6. R1*
7. (R1),
con R1 e R2 espressioni regolari.
Def: se R è espressione regolare, allora L(R) è linguaggio
generato da R.
Esempi di espressioni regolari
Es: A={0, 1},
1. (0 U 1) = {0, 1}
2. 0*10* = {w | w ha un solo 1 }
3. A*1A* = {w | w almeno un 1 }
4. A*001A* = {w | w ha 001 come sottostringa }
5. (AA)* = {w | |w| pari }
6. (AAA)* = {w | |w| multiplo di 3 }
Es:
Sia EVEN-EVEN su A={a, b} insieme stringhe con numero pari
di a e numero pari di b
Es, aababbaaababab in EVEN-EVEN.
espressione regolare:
Teorema di Kleene
Teorema Linguaggio A è regolare sse A ammette una
espressione regolare.