Visualizza wikitesto di Pumping lemma per i linguaggi regolari

Nella [[teoria dei linguaggi formali]] il '''pumping lemma per i linguaggi regolari''' è una condizione necessaria affinché un linguaggio sia [[linguaggio regolare|regolare]]. Viene utilizzato per dimostrare che un linguaggio appartiene ad una classe di [[linguaggi formali]] differente da quella generata da [[grammatica formale|grammatiche formali]] di Tipo 3.

== Definizione formale ==
Sia <math>\mathcal{A} = \left \langle \Sigma, Q, \delta, s_0, F \right \rangle</math> un [[automa a stati finiti]] tale che <math>|Q| = n</math>, sia <math>L(A)</math> il linguaggio riconosciuto dall'automa e sia <math>z \in L(A)</math> tale che <math>|z| \ge n</math>,

È quindi possibile scrivere <math>z = uvw</math> con <math>|uv| \le n</math> e <math>v \ne \varepsilon</math> e quindi <math>uv^{*}w \in L(A)</math>.

== Dimostrazione ==
Sia <math>z = x_1 x_2 \cdots x_k \in L(A)</math>. Poiché <math>|z| \ge n</math> per accettare la stringa ''z'' l'automa deve assumere <math>n+1</math> stati (compreso quello iniziale), ma poiché l'automa possiede esattamente n stati distinti, per il [[principio dei cassetti]], uno degli stati <math>\left \{ q_z0, q_z1, q_z2, \cdots, q_zk \right \}</math> (dove <math>q_zk</math> è lo stato finale in cui la parola viene riconosciuta) deve comparire almeno due volte.

Si supponga che <math>q_zi = q_zj</math>, ovvero i due stati coincidano nell'insieme Q e sia ''v'' la sottostringa di ''z'' tale che <math>\hat{\delta}(q_zi, v) = q_zj</math>.

Poiché <math>z \in L(A)</math> e <math>z = uvw</math>, si ha che tutte le stringhe della forma <math>uv^{k}w</math> con <math>k \ge 0</math> saranno riconosciute dall'automa, ovvero <math>uv^{k}w \in L(A)</math>.

== Bibliografia ==
* {{cita pubblicazione |cognome=Bar-Hillel |nome=Yehoshua |linkautore=Yehoshua Bar-Hillel |coautori=M. A. Perles, E. Shamir |anno=1961 |titolo=On formal properties of simple phrase structure grammars |rivista=Zeitschrift für Phonetik, Sprachwissenschaft und Kommunikationsforschung |volume=14 |pp=143-172 |lingua=inglese}}
* {{cita libro|nome = John E. |cognome = Hopcroft |wkautore = John Hopcroft |coautori = Rajeev Motwani; [[Jeffrey Ullman|Jeffrey D. Ullman]]|titolo = Introduction to Automata Theory, Languages, and Computation|editore = Addison Wesley|anno = 2006|mese=luglio|giorno = 15|lingua = inglese|capitolo = Properties of Regular Languages|ISBN = 978-0-321-46225-1}}
* {{cita libro|nome = Martin |cognome = Davis |wkautore = Martin Davis |coautori = Ron Sigal; Elaine J. Weyuker|titolo = Computability, Complexity, and Languages: Fundamentals of Theoretical Computer Science|editore = Morgan Kaufmann|anno = 1994|mese=febbraio|giorno = 17|lingua = inglese|capitolo = The Pumping Lemma and Its Applications|ISBN = 978-0-12-206382-4}}

== Voci correlate ==
* [[Pumping lemma per i linguaggi liberi dal contesto]]

{{portale|informatica|matematica}}

[[Categoria:Teoria dei linguaggi formali]]
[[Categoria:Lemmi]]
[[Categoria:Teoria degli automi]]