Indietro

ⓘ Pumping lemma per i linguaggi regolari




                                     

ⓘ 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.

                                     

1. Definizione formale

Sia A = ⟨ Σ, Q, δ, s 0, F ⟩ {\displaystyle {\mathcal {A}}=\left\langle \Sigma,Q,\delta,s_{0},F\right\rangle } un automa a stati finiti tale che | Q | = n {\displaystyle |Q|=n}, sia L A {\displaystyle LA} il linguaggio riconosciuto dallautoma e sia z ∈ L A {\displaystyle z\in LA} tale che | z | ≥ n {\displaystyle |z|\geq n},

È quindi possibile scrivere z = u v w {\displaystyle z=uvw} con | u v | ≤ n {\displaystyle |uv|\leq n} e v ≠ ϵ {\displaystyle v\neq \epsilon } e quindi u v ∗ w ∈ L A {\displaystyle uv^{*}w\in LA}.

                                     

2. Dimostrazione

Sia z = x 1 x 2 ⋯ x k ∈ L A {\displaystyle z=x_{1}x_{2}\cdots x_{k}\in LA}. Poiché | z | ≥ n {\displaystyle |z|\geq n} per accettare la stringa z lautoma deve assumere n + 1 {\displaystyle n+1} stati compreso quello iniziale, ma poiché lautoma possiede esattamente n stati distinti, per il principio dei cassetti, uno degli stati { q z 0, q z 1, q z 2, ⋯, q z k } {\displaystyle \left\{q_{z}0,q_{z}1,q_{z}2,\cdots,q_{z}k\right\}} dove q z k {\displaystyle 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 {\displaystyle q_{z}i=q_{z}j}, ovvero i due stati coincidano nellinsieme Q e sia v la sottostringa di z tale che δ ^ q z i, v = q z j {\displaystyle {\hat {\delta }}q_{z}i,v=q_{z}j}.

Poiché z ∈ L A {\displaystyle z\in LA} e z = u v w {\displaystyle z=uvw}, si ha che tutte le stringhe della forma u v k w {\displaystyle uv^{k}w} con k ≥ 0 {\displaystyle k\geq 0} saranno riconosciute dallautoma, ovvero u v k w ∈ L A {\displaystyle uv^{k}w\in LA}.