Dimostrazione con pumping lemma
Salve a tutti avrei bisogno di un parere/correzione riguardo a questa dimostrazione che fa uso del pumping lemma (p.l in seguito). Premetto che è la prima che faccio e non ne sono molto convinto.
TESTO: Dimostrare che non esiste un automa a stati finiti (in seguito ASF) che riconosce il linguaggio delle stringhe binarie che a) iniziano per 1 b)interpretate come numero binario hanno un valore $=2(mod5)$ c)il massimo numero di 1 consecutivi è minore uguale del massimo numero di 0 consecutivi. Ad esempio 10010011, che corsisponde al valore decimale 147, è accettata.
dim(almeno lo spero)
Supponiamo per assurdo che esista un automa A che riconosce il linguaggio in questione (L). Allora esiste $n$ costante del p.l. tale che, $AA$ stringa $w inL$ , con $|w|>=n$,$EE$ una scomposizione$w=xyz$, con $|y|>0, |xy|<=n$, e tale che $AAi>=0$ la stringa $xy^iz$ è ancora riconosciuta da A.
Facendo il disegnino dell'ASF che riconosce il linguaggio caraterizzato solo da a)e b) vedo che, affinchè il valore di una generica stringa $w$ della forma $1^j0^h$ sia congruo a 2 modulo 5, deve essere (condizione sufficiente,non necessaria) $j=3(mod4)$ e $h=1(mod4)$.
Scelgo dunque arbitrariamente (c'è il "per ogni" riguardo alle $w$, giusto?) $w=1^(4n+3) 0^(4(n+1)+1)$, che appartiene a $L$. Ora, ho due possibili generiche scomposizioni di $w$. Se entrambe (dopo aver completato la dimostrazione) mi conducono a un assurdo, ho finito.
1° caso) $x=epsilon$(stringa vuota) $y=1^j$, con $1 4n+5 $ , $AA1
2°caso) $x=1^h$ ,con $1<=h<=n-1$ $y=1^j $, con $1<=j<=n-h$, $z=1^(4n+3-j-h) 0^(4n+5)$. Allo stesso modo,
$xy^iz= 1^(4n+3+(i-1)j) 0^(4n+5)$ dovrebbe essere accettata da A $AAi>=0$, ma per $i=4$ ho che tale stringa non appartiene più a $L$ (non è più rispettata, come sopra, la condizione c)). Ari assurdo. Dunque non esiste tale automa.
Q.E.D.
Sparate pure. Dite tutto tutto quel che vi viene in mente, è probabile che abbia sbagliato totalmente, sono all'inizio e mi servirebbero degli aiuti. Grazie a chiunque risponderà
TESTO: Dimostrare che non esiste un automa a stati finiti (in seguito ASF) che riconosce il linguaggio delle stringhe binarie che a) iniziano per 1 b)interpretate come numero binario hanno un valore $=2(mod5)$ c)il massimo numero di 1 consecutivi è minore uguale del massimo numero di 0 consecutivi. Ad esempio 10010011, che corsisponde al valore decimale 147, è accettata.
dim(almeno lo spero)
Supponiamo per assurdo che esista un automa A che riconosce il linguaggio in questione (L). Allora esiste $n$ costante del p.l. tale che, $AA$ stringa $w inL$ , con $|w|>=n$,$EE$ una scomposizione$w=xyz$, con $|y|>0, |xy|<=n$, e tale che $AAi>=0$ la stringa $xy^iz$ è ancora riconosciuta da A.
Facendo il disegnino dell'ASF che riconosce il linguaggio caraterizzato solo da a)e b) vedo che, affinchè il valore di una generica stringa $w$ della forma $1^j0^h$ sia congruo a 2 modulo 5, deve essere (condizione sufficiente,non necessaria) $j=3(mod4)$ e $h=1(mod4)$.
Scelgo dunque arbitrariamente (c'è il "per ogni" riguardo alle $w$, giusto?) $w=1^(4n+3) 0^(4(n+1)+1)$, che appartiene a $L$. Ora, ho due possibili generiche scomposizioni di $w$. Se entrambe (dopo aver completato la dimostrazione) mi conducono a un assurdo, ho finito.
1° caso) $x=epsilon$(stringa vuota) $y=1^j$, con $1
2°caso) $x=1^h$ ,con $1<=h<=n-1$ $y=1^j $, con $1<=j<=n-h$, $z=1^(4n+3-j-h) 0^(4n+5)$. Allo stesso modo,
$xy^iz= 1^(4n+3+(i-1)j) 0^(4n+5)$ dovrebbe essere accettata da A $AAi>=0$, ma per $i=4$ ho che tale stringa non appartiene più a $L$ (non è più rispettata, come sopra, la condizione c)). Ari assurdo. Dunque non esiste tale automa.
Q.E.D.
Sparate pure. Dite tutto tutto quel che vi viene in mente, è probabile che abbia sbagliato totalmente, sono all'inizio e mi servirebbero degli aiuti. Grazie a chiunque risponderà
Risposte
Ciao! $1^j0^h$, con $j \equiv 3 (mod4)$ e $h\equiv1(mod4)$, non e' congruo a $2$ modulo $5$.
Hai ragione Tom, ho confuso delle frecce..Dovrebbe essere $1^j 0^h$ con $j\equiv3(mod4)$ e $h\equiv0(mod4)$. Cambiando i "numeri", comunque, il modo di procedere va bene? E' proprio la prima dimostrazione che faccio col pumping lemma, non ho termini di paragone...grazie
Allora, avendo una stringa del genere $1^{4n+3}0^{4n+4} \in L$, Sai che di sicuro $y$ contiene solo $1$, quindi facendo il pumping in modo che risultino più $1$ di $0$, così come hai fatto, allora sei a posto.
I linguaggi regolari non possono "contare" il numero di occorrenze di una certa stringa, quindi, generalmente, quando hai $1^n0^m$, con dei vincoli tra $n$ ed $m$ (per esempio $n \le m$), sai che quelle stringhe non possono appartenere a linguaggi regolari. Ciao
I linguaggi regolari non possono "contare" il numero di occorrenze di una certa stringa, quindi, generalmente, quando hai $1^n0^m$, con dei vincoli tra $n$ ed $m$ (per esempio $n \le m$), sai che quelle stringhe non possono appartenere a linguaggi regolari. Ciao
Grazie mille per la conferma! Lo so che a livello intuitivo il motivo è quello, il prof ce l'ha ben spiegato, solo che dovevo dimostrare anche rigorosamente. Grazie ancora per l'aiuto, temevo il post finisse nel dimenticatoio. Spero un giorno di poter ricambiare a tutti questi aiuti. Ciao
Lo so che a livello intuitivo il motivo è quello, il prof ce l'ha ben spiegato, solo che dovevo dimostrare anche rigorosamente. Grazie ancora per l'aiuto, temevo il post finisse nel dimenticatoio. Spero un giorno di poter ricambiare a tutti questi aiuti. Ciao
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo