Pumping lemma per linguaggi regolari

[andreflex]

Salve a tutti fra pochi giorni mi troverò ad affrontare l'esame di linguaggi di programmazione che consiste in alcuni esercizi riguardo i linguaggi formali,sono abbastanza ferrato quasi tutte le tipologie di esercizio tranne in una : il pumping lemma per i linguaggi regolari.
Non riesco proprio a capire come risolvere esercizi che lo richiedono.
Prendiamo ad esempio il semplice linguaggio \(\displaystyle L=a^n b^n | n>=1 \)
Per il P.L so che esiste un automa a stati finiti con n stati che accetta il linguaggio;
z = vwx
w diverso da stringa vuota
|wx|<= n non possono essere e
\(\displaystyle vw^ix \) appartiene al linguaggio per ogni i,i>=0
1) Non capisco perchè ci devono essere ad esempio per il riconoscimento della a n+1 stati;
2) Non capisco dopo aver trovato il ciclo cosa posso fare per dimostrare che il linguaggio non è regolare.
Grazie a chiunque mi aiuterà.

[Branko1]

Spero ti sia ancora utile, comunque :
1 - Perché lo stato + 1 dovrebbe essere quello di errore. Ma la n si riferisce ai simboli non terminali della grammatica.
2 - basta far vedere che ponendo

$
u = \0 ,
v = a,
w = b ,
$

Iterando i si ottiene una stringa del tipo 'aab' che fa parte del linguaggio. Ovviamente il linguaggio che ho compreso io è $a^n b^(n/n)$ ossia $a^n b$.

Se invece il linguaggio era $a^n b^n c^n$ il discorso cambia :

$
u = a,
v = b,
w = c,
$
$ per n= 2, z = a b b c $

In quanto non appartiene al linguaggio.

[Branko1]

Ora ho guardato il codice Tex ed ho capito meglio, (scusate non sono abituato). Allora, $a^n b^n $ non è regolare poiché gli automi a stati finiti non sanno contare. Puoi creare un automa per una n fissata, appunto creando n stati. Ma non per un n qualsiasi, infatti la pila degli automi a pila serve proprio a questo. Non a caso vengono definiti "automi a stati finiti con l'ausilio di una pila". In ogni caso se applichi bene il pumping lemma di tipo 3 vedrai che il linguaggio non è regolare, e invece con il lemma di tipo 2 vedrai che è context-free.