Linguaggi non regolari

Non tutti i linguaggi sono regolari

Consideriamo il seguente linguaggio $L= \{a^nb^n | n \geq 0 \}$

Una macchina che riconosca $L$, per essere in grado di controllare alla fine della lettura dell’input se il numero di $a$ è uguale al numero di $b$, dovrebbe essere in grado di ricordare, mentre legge una stringa, quanti simboli uguali ad $a$ ha letto

Siccome $n$ non è limitato, la macchina dovrebbe tener traccia di un numero illimitato di possibilità

Non può farlo perchè ha un numero finito di stati

Pumping lemma

<aside> 💡 Se $L$ è un linguaggio regolare, allora esiste una costante positiva $p$ tale che per ogni stringa $w$ in $L$ di lunghezza $|w| \geq p$, esistono tre stringhe $x,y,z$ con $w = xyz$ che soddisfano:

1. per ogni $i \geq 0$, $xy^iz \in L$
2. $|y| >0$
3. $|xy| \leq p$ </aside>

• Dimostrazione (idea)

Teorema

<aside> 💡 Il linguaggio $C= \{w | w \text{ ha lo stesso numero di simboli uguali a } 0 \text{ e uguali a }1\}$ non è regolare

</aside>

• Dimostrazione