Definizioni e dimostrazioni

K J

̸

dove x = y, possiamo scrivere x = 1 e y = 1 per alcuni interi K, J, dove

J K J

̸ ∈ ̸

K = J. Prendiamo z = 01 . Allora xz = 1 01 / PAL, poiché K = J, ma

J J J K

∈

yz = 1 01 PAL. Pertanto, 1 e 1 sono distinguibili rispetto a PAL per

̸

ogni K = J. ∗

Definizione (δ per NFAs) ∗ ∗

× → P(Q)

Sia M = (Q, Σ, q , δ, A) un NFA. Si definisce δ : Q Σ in modo

0

ricorsivo come segue: ∗

∈ {q}.

1. Per ogni q Q, δ (q, ϵ) =

∗

∈ ∈ ∈

2. Per ogni y Σ , a Σ, e q Q, [

∗

δ (q, ya) = δ(p, a)

∗

p∈δ (q,y)

Definizione (linguaggio accettato da un NFA)

∗ ∩

Sia M = (Q, Σ, q , δ, A) un NFA. Una stringa x è accettata da M se δ (q , x)

0 0

̸ ∅. {x|x }.

A = Il linguaggio accettato da M è il linguaggio L(M ) = è accettata da M

∗

Se L è un linguaggio in Σ , allora L è accettato da M se L = L(M ).

Definizione (NFA con ϵ-transizioni)

Un automa finito non deterministico con ϵ-transizioni (abbreviato ϵ-NFA) è una

∈ ⊆

5-tupla (Q, Σ, q , δ, A), dove Q e Σ sono insiemi finiti non vuoti, q Q, A Q,

0 0

× ∪ {ϵ}) → P(Q).

e δ : Q (Σ ∗

∈ ∈

Per x Σ e p Q:

∗ {q ∈ |

δ (p, x) = Q esiste una sequenza di transizioni corrispondenti a x}.

per cui M si sposta da p a q. 3

∗

Definizione (δ non ricorsivo per ϵ-NFA)

∗

∈ ∈

Sia M = (Q, Σ, q , δ, A) un ϵ-NFA. Se x = a a . . . a Σ e p, q Q, diciamo

0 1 2 n

che M si sposta dallo stato p allo stato q attraverso una sequenza di transizioni

≥ ∈

corrispondenti a x se esiste un intero m n, una sequenza b , b , . . . , b

1 2 m

∪ {ϵ}

Σ tale che b b . . . b = x, e una sequenza di stati p = p , p , . . . , p = q

1 2 m 0 1 m

≤ ≤ ∈

tale che per ogni i dove 1 i m, p δ(p , b ).

i i−1 i

∗

∈ ∈

Per x Σ e p Q:

∗ {q ∈ |

δ (p, x) = Q esiste una sequenza di transizioni corrispondenti a x per cui M si sposta da p a q}.

∗

Definizione (δ per NFAs) ∗ ∗ → P(Q)

Sia M = (Q, Σ, q , δ, A) un NFA. Si definisce δ : Q×Σ ricorsivamente

0

come segue: ∗

∈ {q}.

1. Per ogni q Q, δ (q, ϵ) =

∗

∈ ∈ ∈

2. Per ogni y Σ , a Σ, e q Q, [

∗

δ (q, ya) = δ(p, a)

∗

p∈δ (q,y)

Definizione (Chiusura ϵ di un insieme di stati)

Sia M = (Q, Σ, q , δ, A) un ϵ-NFA. Per un sottoinsieme S di Q, la chiusura ϵ di

0

S, indicata come ϵ(S), è il sottoinsieme di Q definito ricorsivamente come segue:

1. Ogni elemento di S è un elemento di ϵ(S).

∈

2. Per ogni q ϵ(S), ogni elemento di δ(q, ϵ) è un elemento di ϵ(S).

3. Nessun elemento di Q è in ϵ(S) a meno che non possa essere ottenuto

utilizzando le regole 1 e 2. ∗

Definizione (definizione ricorsiva di δ per un ϵ-

NFA) ∗ ×

Sia M = (Q, Σ, q , δ, A) un ϵ-NFA. La funzione di transizione estesa δ : Q

0

∗ → P(Q)

Σ è definita come segue:

∗

∈

1. Per ogni q Q, δ (q, ϵ) = ϵ({q}).

∗

∈ ∈ ∈

2. Per ogni q Q, y Σ , e a Σ:  

[

∗

δ (q, ya) = ϵ δ(p, a)

 

∗

p∈δ (q,y)

4

∗ ̸ ∅.

Una stringa x è accettata da M se δ (q , x)∩A = Il linguaggio riconosciuto

0

∗

{x ∈ | }.

da M è L(M ) = Σ x è accettata da M

∗

Definizione (δ per NFAs) ∗ ∗

× → P(Q)

Sia M = (Q, Σ, q , δ, A) un NFA. Si definisce δ : Q Σ in modo

0

ricorsivo come segue: ∗

∈ {q}.

1. Per ogni q Q, δ (q, ϵ) =

∗

∈ ∈ ∈

2. Per ogni y Σ , a Σ, e q Q: [

∗

δ (q, ya) = δ(p, a)

∗

p∈δ (q,y)

Definizione (NFA con transizioni ϵ)

Un automa finito non deterministico con transizioni ϵ (abbreviato ϵ-NFA) è una

∈ ⊆

5-tupla (Q, Σ, q , δ, A), dove Q e Σ sono insiemi finiti non vuoti, q Q, A Q,

0 0

× ∪ {ϵ}) → P(Q).

e δ : Q (Σ

Definizione (Chiusura ϵ di un insieme di stati)

Sia M = (Q, Σ, q , δ, A) un ϵ-NFA. Per un sottoinsieme S di Q, la chiusura ϵ di

0

S, indicata come ϵ(S), è il sottoinsieme di Q definito ricorsivamente come segue:

1. Ogni elemento di S è un elemento di ϵ(S).

∈

2. Per ogni q ϵ(S), ogni elemento di δ(q, ϵ) è un elemento di ϵ(S).

3. Nessun elemento di Q è in ϵ(S) a meno che non possa essere ottenuto

utilizzando le regole 1 e 2. ∗

Definizione (definizione ricorsiva di δ per un ϵ-

NFA) ∗ ×

Sia M = (Q, Σ, q , δ, A) un ϵ-NFA. La funzione di transizione estesa δ : Q

0

∗ → P(Q)

Σ è definita come segue:

∗

∈

1. Per ogni q Q, δ (q, ϵ) = ϵ({q}).

∗

∈ ∈ ∈

2. Per ogni q Q, y Σ , e a Σ: [

∗

δ (q, ya) = ϵ(δ(p, a)).

∗

p∈δ (q,y)

5

Teorema (equivalenza di ϵ-NFA e NFA)

∗

⊆

Teorema: Sia L Σ e supponiamo che L sia riconosciuto dall’ϵ-NFA M =

(Q, Σ, q , δ, A). Esiste un NFA M = (Q , Σ, q , δ , A ) che lo riconosce.

0 1 1 1 1 1

Dimostrazione: Scomponiamo la dimostrazione in tre componenti princi-

pali. Prima elimineremo le transizioni ϵ, quindi mostreremo che la nuova fun-

∗ ∗

zione di transizione δ è equivalente alla δ originale, e infine che L(M ) = L(M ).

1

1

Definizione di M (eliminazione delle transizioni ϵ): Iniziamo de-

1

finendo Q = Q e q = q . Il problema consiste nel definire la nuova funzione di

1 1 0

transizione δ in modo che, se M può passare dallo stato p allo stato q usando

1

certi simboli con transizioni ϵ, allora in M possiamo passare da p a q usando

1

solo quei simboli senza transizioni ϵ.

Essenzialmente abbiamo già la soluzione come risultato della definizione di

∗ ∈ ∈

δ per l’ϵ-NFA M . Per ogni q Q e a Σ, definiamo:

∗

δ (q, a) = δ (q, a).

1

Quello che abbiamo fatto è definire δ in modo che se M può passare da p

1

a q usando l’input a e le transizioni ϵ, allora M può passare da p a q usando

1

solo a.

Teorema (equivalenza di ϵ-NFA e NFA, continu-

azione)

Cosa succede per gli stati di accettazione A ? A = A è sufficiente? Quasi,

1 1

l’unica eccezione è se c’è un percorso da q a uno stato di accettazione usando

0

solo transizioni ϵ: ( ∪ {q } }) ∩ ̸ ∅

A se ϵ({q A =

0 0

A =

1 A altrimenti

∗ ∗

∈

Ora, se x Σ , δ (q, x) è l’insieme degli stati che M può raggiungere

1

1 ∗

partendo da q e usando i simboli di x. δ (q, x) è l’insieme degli stati che M può

raggiungere usando i simboli di x e le transizioni ϵ.

Per completare la nostra dimostrazione che L(M ) = L(M ) dimostriamo per

1

∗ ∗ ∗

∈ |x| ≥ ≥

induzione che δ (q, x) = δ (q, x) per tutti x Σ dove 1 (perché 1?).

1

Teorema (equivalenza di NFAs e DFAs)

∗

⊆

Teorema: Sia L Σ e supponiamo che L sia accettato da un NFA M =

1

(Q , Σ, q , δ , A ). Allora esiste un DFA M = (Q , Σ, q , δ , A ) tale che L(M ) =

1 1 1 1 2 2 2 2 2 2

L(M ) = L.

1

Dimostrazione: Il DFA M è definito dai suoi componenti:

2

• P(Q

Q = ) (l’insieme dei sottoinsiemi di Q )

2 1 1

6

• {!q }

q =

2 1

• ∈ ∈ ∈

δ (q, a) = δ (p, a) per q Q e a Σ dove p q

2 1 2

• {q ∈ | ∩ ̸ ∅}

A = Q q A =

2 2 1

Nota che gli stati che definiamo nel nostro DFA sono insiemi di stati dell’NFA

originale. Questo va bene, poiché la nostra δ prende esattamente ciò che

dovrebbe: un singolo elemento da Q (che nel nostro caso è un insieme), e

2

un simbolo da Σ. Restituisce anche ciò che dovrebbe: un singolo elemento da

Q (che di nuovo, è un insieme). M come definito è un DFA.

2 2

Dimostreremo ora che M riconosce L. Ciò è fatto mostrando che:

2

∗ ∗ ∗

∈

δ (q , x) = δ (q , x) per ogni x Σ .

2 1

2 1

|x|

Quando = 0: ∗ ∗

δ (q , x) = δ (q , ε) = q

2 2 2

2 2 ∗ ∗

{q }

= = δ (q , ε) = δ (q , x).

1 1 1

1 1

∗

(per definizione di δ per DFA) (per la nostra definizione di q ) (per definizione

2

∗

di δ per NFA) ≥ |x|

L’ipotesi induttiva in questo caso è che K 0 e che per ogni x con = K,

∗ ∗ ∗

|x|

δ (q , x) = δ (q , x). Dobbiamo mostrare che se = K + 1, allora δ (q , x) =

2 1 2

2 1 2

∗ |y|

δ (q , x). Scriviamo innanzitutto x = ya, dove = K.

1

1

Teorema (equivalenza di NFAs e DFAs - contin-

uazione)

Quindi: ∗ ∗

δ (q , x) = δ (q , ya)

2 2

2 2 ∗

= δ (δ (q , y), a)

2 2

2

∗

= δ (!δ (q , y), a) = δ (p, a)

2 2 1

1

∗ ∗ ∗

∈

p δ (q , y) = δ (q , ya) = δ (q , x).

1 1 1

1 1 1

È facile vedere ora che M e M accettano lo stesso linguaggio:

1 2

∗

⇔ ∈

M accetta x δ (q , x) A

2 2 2

2

∗

⇔ ∩ ̸ ∅

δ (q , x) A = (per definizione di A )

2 1 2

2

∗

⇔ ∩ ̸ ∅

δ (q , x) A = (per induzione sopra)

1 1

1

⇔ M accetta x.

1 7

Teorema (chiusura dei linguaggi regolari sotto la

concatenazione)

∗

⊆

Sia L , L Σ e supponiamo che L sia accettato da un DFA M = (Q , Σ, q , δ , A )

1 2 1 1 1 1 1 1

e L da un DFA M = (Q , Σ, q , δ , A ). Allora la concatenazione L L è

2 2 2 2 2 2 1 2

anch&rsquo