[Esercizio] Pumping Lemma per i linguaggi regolari

Messaggioda mike.96 » 25/08/2016, 20:44

Salve a tutti, ho da poco iniziato a dimostrare con il Pumping Lemma che i linguaggi non sono regolari.

Ho il seguente linguaggio: $L={0^i 1^j | i,j>0 \wedge 2i>j}$
Suppongo $L$ sia regolare, allora $\exists N>0$ tale che $\forall z \in L$ con $|z| \geq N$ allora $z$ può essere scritta come $z=uvw$.

Suppongo che $z=0^N 1^N$, allora $|z|=2N \Rightarrow |z| \geq N$.
Suppongo che $v=0^h$ tale che $0 < h \leq N$.

Con $k=N+1$, $z_{N+1}=uv^{N+1} w = 0^N 1^{N-h+h(N+1)}$, quindi $2N>N-h+h(N+1) \Leftrightarrow 2N>N+hN$ e $\forall h > 0$ la disuguaglianza non è verificata: $z \notin L$ e quindi non è un linguaggio regolare.

Vorrei sapere se il procedimento che ho svolto è corretto. Grazie a chiunque mi aiuti.
mike.96
Starting Member
Starting Member
 
Messaggio: 8 di 26
Iscritto il: 24/06/2016, 15:22

Torna a Informatica

Chi c’è in linea

Visitano il forum: Nessuno e 1 ospite