Discussione:Pumping lemma per i linguaggi regolari

Aggiunta della definizione di Hopcroft e altra modifica

Definizione formale
Propongo di inserire anche la definizione del libro di Hopcroft (inserito già nella bibliografia) a pagina 126 del pumping lemma in quanto diversa e non necessita dell'utilizzo degli automi, essa si basa sul percorso che prevede di fare prima le grammatiche formali, poi i linguaggi e teoremi relativi e successivamente la trattazione degli automi. Oppure la trattazione degli automi prima ma con enunciazione del pumping lemma in funzione della grammatica e del linguaggio senza utilizzare gli automi (in un corso di informatica teorica, dove questo argomenti è trattato). Propongo di inserirla ovviamente utilizzando stessa notazione della precedente, essa è questa:

Sia $L$ un linguaggio regolare. Allora esiste una costante $i$ tale che per ogni $z\in L$ con $|z|\geq i$, è possibile esprimere $z$ come $z=uvw$, tale che:

1. $v\neq \epsilon$;
2. $|uv|\leq i$;
3. $\forall k\geq 0$ si ha che $uv^{k}z\in L$.<ref>

Aggiunta della dicitura lemma
Propongo anche di correggere la dicitura iniziale in "il pumping lemma è un lemma che sancisce una condizione necessaria...", infatti esso non è solamente una condizione ma è un lemma (o come anche alcuni libri della biografia dicono teorema), la condizione necessaria è in esso contenuta e viene utilizzata come scritto anche nella pagina, per dimostrare che un linguaggio è o non è regolare. Oppure per evitare ripetizioni potremmo scrivere "il pumping lemma sancisce una condizione necessaria...". — Questo commento senza la firma utente è stato inserito da Amilcare-barca (discussioni · contributi) 21:49, 17 mar 2019 (CET).

due appunti veloci:

• lemma lo farei puntare a lemma
• ok l'enunciato, ma anche all'inizio della dimostrazione si può iniziare dicendo: "Sia A = ... un automa a stati finiti che riconosce il linguaggio L"

mi viene il dubbio se è necessario espressamente citare il fatto che tale automa deve essere minimale. aggiungo che la voce inglese si dilunga sul fatto che è una condizione necessaria ma non sufficiente per dimostrare la regolarità di un linguaggio. --valepert 21:52, 22 mar 2019 (CET)