A-PDF Merger DEMO : Purchase from www.A-PDF.com to remove the watermark
Pumping Lemma
Enunciato ||
∃ ) ∀ ∈ ≥ , ∃
Sia un linguaggio regolare, allora (dipendente da tale che con una
=
scomposizione di in tre stringhe con le seguenti tre proprietà:
≠
1. || ≤
2.
∀ ≥ 0 ∈
3. si ha che
Dimostrazione ⟨,
= Σ, , , ⟩ () = .
Essendo un linguaggio regolare, allora esiste un DFA tale che Poniamo la
0
||. ||
= ∈ = ≥ , = …
costante di pumping Sia tale che con quindi .
1
̂ ̂
∀ℎ = 1, … , = ( , … ) = ( , ) = , … ,
sia e sia . Allora è la sequenza di stati che
ℎ 0 1 ℎ 0 0 0 0
1 2 −1
, → → … → → ∈ []
accettano cioè la computazione è . Si noti che e che la
0 1 −1
+ 1
computazione contiene stati.
= || + 1 ≥ ),
Dal momento che abbiamo solo stati, ma la computazione contiene stati (con ne
+ 1
deduciamo che ci deve essere uno stato in che compare almeno due volte nelle prime posizioni
, … , ,
della sequenza, cioè in . Esistono allora due indici tali che:
0
= []
1.
0 ≤ < ≤ []
2. ,
Speziamo in tre stringhe e così fatte:
• ̂ (
= … = , ) []
, quindi
1 0
• ̂ ̂ (̂ ̂
1
( ( (
= … = , ) ≝ , ), ) = , ) []
quindi
+1 0 0
• ̂ ̂ (̂ ̂
1
( ( (
= … = , ) ≝ , ), ) = , ) ≝
quindi
+1 0 0
̂ (̂ ̂
2
( , ), ) = , ) []
(
Graficamente abbiamo
Verifichiamo ora che valgono le tre proprietà del lemma:
< [5], = … ≠ .
1. Dato che per deve contenere almeno un simbolo, quindi
+1
||
≤ [5], = … … ≤
| |
2. Da
-
![Teorema, Pasolini]()
Teorema, Pasolini
-
![Teorema concavità + Teorema di Taylor]()
Teorema concavità + Teorema di Taylor
-
![Conduttori teorema di coulomb]()
Conduttori teorema di coulomb
-
![Teorema del Dini]()
Teorema del Dini
Recensioni
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo
