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 regolare. Viene utilizzato per dimostrare che un linguaggio appartiene ad una classe di linguaggi formali differente da quella generata da grammatiche formali di Tipo 3.

Definizione formale

Sia ${\mathcal {A}}=\left\langle \Sigma ,Q,\delta ,s_{0},F\right\rangle$ un automa a stati finiti tale che $|Q|=n$, sia $L(A)$ il linguaggio riconosciuto dall'automa e sia $z\in L(A)$ tale che $|z|\geq n$,

È quindi possibile scrivere $z=uvw$ con $|uv|\leq n$ e $v\neq \varepsilon$ e quindi $uv^{*}w\in L(A)$.

Dimostrazione

Sia $z=x_{1}x_{2}\cdots x_{k}\in L(A)$. Poiché $|z|\geq n$ per accettare la stringa z l'automa deve assumere $n+1$ stati (compreso quello iniziale), ma poiché l'automa possiede esattamente n stati distinti, per il principio dei cassetti, uno degli stati $\left\{q_{z}0,q_{z}1,q_{z}2,\cdots ,q_{z}k\right\}$ (dove $q_{z}k$ è lo stato finale in cui la parola viene riconosciuta) deve comparire almeno due volte.

Si supponga che $q_{z}i=q_{z}j$, ovvero i due stati coincidano nell'insieme Q e sia v la sottostringa di z tale che ${\hat {\delta }}(q_{z}i,v)=q_{z}j$.

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

Bibliografia

• (EN) Yehoshua Bar-Hillel, M. A. Perles, E. Shamir, On formal properties of simple phrase structure grammars, in Zeitschrift für Phonetik, Sprachwissenschaft und Kommunikationsforschung, vol. 14, 1961, pp. 143-172.
• (EN) John E. Hopcroft, Rajeev Motwani; Jeffrey D. Ullman, Properties of Regular Languages, in Introduction to Automata Theory, Languages, and Computation, Addison Wesley, 15 luglio 2006, ISBN 978-0-321-46225-1.
• (EN) Martin Davis, Ron Sigal; Elaine J. Weyuker, The Pumping Lemma and Its Applications, in Computability, Complexity, and Languages: Fundamentals of Theoretical Computer Science, Morgan Kaufmann, 17 febbraio 1994, ISBN 978-0-12-206382-4.

Voci correlate

• Pumping lemma per i linguaggi liberi dal contesto