Pumping Lemma per linguaggi regolari
Innanzitutto buon pomeriggio!
Ho svolto alcuni esercizi sul Pumping Lemma per i linguaggi regolari che propongo di seguito.
Dimostrare che i seguenti linguaggi non sono regolari:
1)[tex]L=\left\{0^n10^n \mid n \geq 1\right\}[/tex]
[tex]w = 0^k10^k[/tex], [tex]xy[/tex] è un prefisso di [tex]0^k[/tex] dovendo essere [tex]|{xy}| \leq k \wedge y \neq \epsilon[/tex].
Ora da [tex]w=xy^iz[/tex] con [tex]i=0[/tex] si ha [tex]w=xz=0^{k-h}10^k[/tex] si ottiene [tex]\forall h \geq 1[/tex][tex]k-h \neq k \Rightarrow w \notin L[/tex]. Da questo l'irregolarità di [tex]L[/tex].
2)[tex]L=\left\{0^n1^m2^n \mid \textit{m e n sono interi arbitrari}\right\}[/tex]
[tex]w=0^k1^g2^k[/tex], [tex]xy[/tex] è un prefisso di [tex]0^k[/tex] dovendo essere [tex]|{xy}| \leq k \wedge y \neq \epsilon[/tex].
Ora da [tex]w=xy^iz[/tex] con [tex]i=0[/tex] si ha [tex]w=xz=0^{k-h}1^g2^k[/tex] si ottiene [tex]\forall h \geq 1[/tex][tex]k-h \neq k \Rightarrow w \notin L[/tex]. Da questo l'irregolarità di [tex]L[/tex].
3)[tex]L=\left\{0^n1^m \mid n \leq m\right\}[/tex]
[tex]w=0^k1^l[/tex], [tex]xy[/tex] è un prefisso di [tex]0^k[/tex] dovendo essere [tex]|{xy}| \leq k \wedge y \neq \epsilon[/tex].
Ora da [tex]w=xy^iz[/tex] con [tex]i=l[/tex] si ha [tex]w=xz=0^{k-h}1^lh1^l[/tex] si ottiene [tex]k-h+lh \leq l \Leftrightarrow l=1\wedge k=1 \vee k=0 \Rightarrow \forall l \in \mathbb{N} \setminus \left\{0,1\right\} \wedge \forall h \geq 1 w \notin L[/tex]. Da questo l'irregolarità di [tex]L[/tex].
4)[tex]L=\left\{0^n \mid \textit{n e' un quadrato perfetto}\right\}[/tex]
Pongo [tex]\sqrt{n}=k[/tex] ed ottengo [tex]w=0^{k^2}=(0^k0^k...0^k)^k[/tex]
Ora da [tex]w=xy^iz[/tex] con [tex]i=0[/tex] si ha [tex]w=xz=0^{k-h}0^{k(k-1)}[/tex] si ottiene [tex]\forall h \geq 1 k-h+k(k-1) \neq k^2 \Rightarrow \forall h \geq 1 k^2 - h \neq k^2 \Rightarrow w \notin L[/tex]. Da questo l'irregolarità di [tex]L[/tex].
5)[tex]L=\left\{0^n \mid \textit{n e' un cubo perfetto}\right\}[/tex]
Pongo [tex]\sqrt[3]{n}=k[/tex] ed ottengo [tex]w=0^{k^3}[/tex]
Ora da [tex]w=xy^iz[/tex] con [tex]i=0[/tex] si ha [tex]w=xz=0^{k-h}0^{k(k^2-1)}[/tex] si ottiene [tex]\forall h \geq 1 k-h+k(k^2-1) \neq k^3 \Rightarrow \forall h \geq 1 k^3 - h \neq k^3 \Rightarrow w \notin L[/tex]. Da questo l'irregolarità di [tex]L[/tex].
6)[tex]L=\left\{w \in \left\{0,1\right\}^{*} \mid \textit{la lunghezza di w e' un quadrato perfetto} \right\}[/tex]
[tex]w=((0+1)^k(0+1)^k...(0+1)^k)^k[/tex], [tex]xy[/tex] è un prefisso di [tex](0+1)^k[/tex] dovendo essere [tex]|{xy}| \leq k \wedge y \neq \epsilon[/tex].
Ora da [tex]w=xy^iz[/tex] con [tex]i=0[/tex] si ha [tex]w=xz=(0+1)^{k-h}(0+1)^{k(k-1)}[/tex] si ottiene [tex]\forall h \geq 1[/tex][tex]k-h +k(k-1) \neq k^2 \Rightarrow \forall h \geq 1[/tex][tex]k^2 - h \neq k^2 \Rightarrow w \notin L[/tex]. Da questo l'irregolarità di [tex]L[/tex].
7)[tex]L=\left\{0^n \mid \textit{n e' una potenza di 2}\right\}[/tex]
Suppongo [tex]n=2^m[/tex] e pongo [tex]k = n-1[/tex]
[tex]w=0^{2^k}0^{2^k}[/tex], [tex]xy[/tex] è un prefisso di [tex]0^{2^k}[/tex] dovendo essere [tex]|{xy}| \leq 2^k \wedge y \neq \epsilon[/tex].
Ora da [tex]w=xy^iz[/tex] con [tex]i=0[/tex] si ha [tex]w=xz=0^{2^k - 2^h}0^{2^k}[/tex] si ottiene [tex]\forall h \geq 1[/tex][tex]2^k - 2^h + 2^k = 2 \cdot 2^k - 2^h = 2^{k+1} - 2^h[/tex] ed essendo [tex]k=n-1[/tex] \Rightarrow \forall h \geq 1[/tex][tex]2^n - 2^h \neq 2^n \Rightarrow w \notin L[/tex]. Da questo l'irregolarità di [tex]L[/tex].
8)[tex]L =\left\{ w \mid \textit{w e' la concatenazione di due stringhe uguali appartenenti a } {\left\{0,1\right\}}^{*} \right\}[/tex]
[tex]w={w}_{1}{w}_{2} \wedge {w}_{1}=(0 +1)^k \wedge {w}_{1} = {w}_{2}[/tex], scegliendo ad esempio [tex]{w}_{1}=0^k1^j[/tex] segue che [tex]xy[/tex] è un prefisso di [tex]0^k[/tex] dovendo essere [tex]|{xy}| \leq k \wedge y \neq \epsilon[/tex]
Ora da [tex]w=xy^iz[/tex] con [tex]i=0[/tex] si ha [tex]w=xz=0^{k-h}1^j0^k1^j[/tex] si ottiene [tex]\forall h \geq 1[/tex][tex]k-h + j \neq k + j \Rightarrow \forall h \geq 1[/tex][tex]2(k - h + j) \neq 2(k + j) \Rightarrow w \notin L[/tex]. Da questo l'irregolarità di [tex]L[/tex].
Vi chiedo se cortesemente potete dare un'occhiata alla risoluzione ed in caso di errore segnalarmelo...
Riguardo il 7° sono parecchio dubbioso del passaggio [tex]|{xy}| \leq 2^k[/tex] anche se effettivamente [tex]2^k[/tex] dipende pur sempre da [tex]k[/tex] e non vedo altro modo di dimostrare l'irregolarità di tale linguaggio mediante il Pumping Lemma.
Grazie e di nuovo buon pomeriggio!
Ho svolto alcuni esercizi sul Pumping Lemma per i linguaggi regolari che propongo di seguito.
Dimostrare che i seguenti linguaggi non sono regolari:
1)[tex]L=\left\{0^n10^n \mid n \geq 1\right\}[/tex]
[tex]w = 0^k10^k[/tex], [tex]xy[/tex] è un prefisso di [tex]0^k[/tex] dovendo essere [tex]|{xy}| \leq k \wedge y \neq \epsilon[/tex].
Ora da [tex]w=xy^iz[/tex] con [tex]i=0[/tex] si ha [tex]w=xz=0^{k-h}10^k[/tex] si ottiene [tex]\forall h \geq 1[/tex][tex]k-h \neq k \Rightarrow w \notin L[/tex]. Da questo l'irregolarità di [tex]L[/tex].
2)[tex]L=\left\{0^n1^m2^n \mid \textit{m e n sono interi arbitrari}\right\}[/tex]
[tex]w=0^k1^g2^k[/tex], [tex]xy[/tex] è un prefisso di [tex]0^k[/tex] dovendo essere [tex]|{xy}| \leq k \wedge y \neq \epsilon[/tex].
Ora da [tex]w=xy^iz[/tex] con [tex]i=0[/tex] si ha [tex]w=xz=0^{k-h}1^g2^k[/tex] si ottiene [tex]\forall h \geq 1[/tex][tex]k-h \neq k \Rightarrow w \notin L[/tex]. Da questo l'irregolarità di [tex]L[/tex].
3)[tex]L=\left\{0^n1^m \mid n \leq m\right\}[/tex]
[tex]w=0^k1^l[/tex], [tex]xy[/tex] è un prefisso di [tex]0^k[/tex] dovendo essere [tex]|{xy}| \leq k \wedge y \neq \epsilon[/tex].
Ora da [tex]w=xy^iz[/tex] con [tex]i=l[/tex] si ha [tex]w=xz=0^{k-h}1^lh1^l[/tex] si ottiene [tex]k-h+lh \leq l \Leftrightarrow l=1\wedge k=1 \vee k=0 \Rightarrow \forall l \in \mathbb{N} \setminus \left\{0,1\right\} \wedge \forall h \geq 1 w \notin L[/tex]. Da questo l'irregolarità di [tex]L[/tex].
4)[tex]L=\left\{0^n \mid \textit{n e' un quadrato perfetto}\right\}[/tex]
Pongo [tex]\sqrt{n}=k[/tex] ed ottengo [tex]w=0^{k^2}=(0^k0^k...0^k)^k[/tex]
Ora da [tex]w=xy^iz[/tex] con [tex]i=0[/tex] si ha [tex]w=xz=0^{k-h}0^{k(k-1)}[/tex] si ottiene [tex]\forall h \geq 1 k-h+k(k-1) \neq k^2 \Rightarrow \forall h \geq 1 k^2 - h \neq k^2 \Rightarrow w \notin L[/tex]. Da questo l'irregolarità di [tex]L[/tex].
5)[tex]L=\left\{0^n \mid \textit{n e' un cubo perfetto}\right\}[/tex]
Pongo [tex]\sqrt[3]{n}=k[/tex] ed ottengo [tex]w=0^{k^3}[/tex]
Ora da [tex]w=xy^iz[/tex] con [tex]i=0[/tex] si ha [tex]w=xz=0^{k-h}0^{k(k^2-1)}[/tex] si ottiene [tex]\forall h \geq 1 k-h+k(k^2-1) \neq k^3 \Rightarrow \forall h \geq 1 k^3 - h \neq k^3 \Rightarrow w \notin L[/tex]. Da questo l'irregolarità di [tex]L[/tex].
6)[tex]L=\left\{w \in \left\{0,1\right\}^{*} \mid \textit{la lunghezza di w e' un quadrato perfetto} \right\}[/tex]
[tex]w=((0+1)^k(0+1)^k...(0+1)^k)^k[/tex], [tex]xy[/tex] è un prefisso di [tex](0+1)^k[/tex] dovendo essere [tex]|{xy}| \leq k \wedge y \neq \epsilon[/tex].
Ora da [tex]w=xy^iz[/tex] con [tex]i=0[/tex] si ha [tex]w=xz=(0+1)^{k-h}(0+1)^{k(k-1)}[/tex] si ottiene [tex]\forall h \geq 1[/tex][tex]k-h +k(k-1) \neq k^2 \Rightarrow \forall h \geq 1[/tex][tex]k^2 - h \neq k^2 \Rightarrow w \notin L[/tex]. Da questo l'irregolarità di [tex]L[/tex].
7)[tex]L=\left\{0^n \mid \textit{n e' una potenza di 2}\right\}[/tex]
Suppongo [tex]n=2^m[/tex] e pongo [tex]k = n-1[/tex]
[tex]w=0^{2^k}0^{2^k}[/tex], [tex]xy[/tex] è un prefisso di [tex]0^{2^k}[/tex] dovendo essere [tex]|{xy}| \leq 2^k \wedge y \neq \epsilon[/tex].
Ora da [tex]w=xy^iz[/tex] con [tex]i=0[/tex] si ha [tex]w=xz=0^{2^k - 2^h}0^{2^k}[/tex] si ottiene [tex]\forall h \geq 1[/tex][tex]2^k - 2^h + 2^k = 2 \cdot 2^k - 2^h = 2^{k+1} - 2^h[/tex] ed essendo [tex]k=n-1[/tex] \Rightarrow \forall h \geq 1[/tex][tex]2^n - 2^h \neq 2^n \Rightarrow w \notin L[/tex]. Da questo l'irregolarità di [tex]L[/tex].
8)[tex]L =\left\{ w \mid \textit{w e' la concatenazione di due stringhe uguali appartenenti a } {\left\{0,1\right\}}^{*} \right\}[/tex]
[tex]w={w}_{1}{w}_{2} \wedge {w}_{1}=(0 +1)^k \wedge {w}_{1} = {w}_{2}[/tex], scegliendo ad esempio [tex]{w}_{1}=0^k1^j[/tex] segue che [tex]xy[/tex] è un prefisso di [tex]0^k[/tex] dovendo essere [tex]|{xy}| \leq k \wedge y \neq \epsilon[/tex]
Ora da [tex]w=xy^iz[/tex] con [tex]i=0[/tex] si ha [tex]w=xz=0^{k-h}1^j0^k1^j[/tex] si ottiene [tex]\forall h \geq 1[/tex][tex]k-h + j \neq k + j \Rightarrow \forall h \geq 1[/tex][tex]2(k - h + j) \neq 2(k + j) \Rightarrow w \notin L[/tex]. Da questo l'irregolarità di [tex]L[/tex].
Vi chiedo se cortesemente potete dare un'occhiata alla risoluzione ed in caso di errore segnalarmelo...
Riguardo il 7° sono parecchio dubbioso del passaggio [tex]|{xy}| \leq 2^k[/tex] anche se effettivamente [tex]2^k[/tex] dipende pur sempre da [tex]k[/tex] e non vedo altro modo di dimostrare l'irregolarità di tale linguaggio mediante il Pumping Lemma.
Grazie e di nuovo buon pomeriggio!
Risposte
Up!!
Up!!
Ciao.
Ho controllato sul M.Sipser l'enunciato del Pumping Lemma e credo tu faccia un piccolo errore. Infatti il teorema dice:
Se $A$ è un linguaggio regolare, allora esiste un numero $k$ (sul testo indicato con $p$), tale che, per ogni stringa $w \in A$ di lunghezza almeno $k$ esiste una scomposizione $w = xyz$ tale che si verifichino le seguenti:
Ho controllato sul M.Sipser l'enunciato del Pumping Lemma e credo tu faccia un piccolo errore. Infatti il teorema dice:
Se $A$ è un linguaggio regolare, allora esiste un numero $k$ (sul testo indicato con $p$), tale che, per ogni stringa $w \in A$ di lunghezza almeno $k$ esiste una scomposizione $w = xyz$ tale che si verifichino le seguenti:
Per ogni $i$, $xy^{i}z \in A$;
$y \neq \epsilon$;
$|xy|
Dunque, quando fai gli esercizi ragionando per assurdo che $A$ sia un linguaggio regolare, devi supporre che esista un certo $k$ e non porlo uguale a certe quantità, così come fai appunto in (4), (5) e (7). A quel punto prendi una parola $w \in A$ che sia lunga almeno $k$ e dimostri l'assurdo.
Però, secondo me, aggiustando queste sottigliezze i ragionamenti filano.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo