[Generico] Esercizio Pumping Lemma linguaggi Regolari

[pier_IP]

Ciao, potete aiutarmi in questo esercizio?
Sia $ L = {a^n b^m c^k | m>k; m, n, k>=1} $ dimostrare che non è regolare

Per quanto ho capito, il PL si applica prendendo una stringa $z \in L$ e si deve scomporre questa z in 3 parti in modo che risulti $z = uvw$ e aumentando a random il numero di v (pompaggio) la stringa continua ad appartenere al linguaggio $\forall t>=0 : u v^t w \in L$.
Quindi devo considerare tutte le possibili scomposizioni di z e per ogni scomposizione se (s)pompando si ottiene una stringa non appartenente al linguaggio, allora il linguaggio non è regolare.

Con questa idea generale però se prendo la scomposizione $u = a^i; v=a^(m-i); w=b^m c^k $ (con $i

Cita

Segnala

---

Risposte

MenoInfinito

13 mag 2013, 07:51

Devi trovare una stringa che possa essere un valido controesempio e che in qualunque modo venga decomposta dia luogo, col pompaggio, ad una stringa non appartenente al linguaggio.

Di primo acchito... se prendi z = abbc dovresti aver trovato una stringa appartente al L ma che in qualunque modo venga decomposta non apparterra', post pompaggio, ad L (Per i = 0).
Dai un'occhiata.

Cita

Segnala

---

pier_IP

16 mag 2013, 16:34

Ciao grazie della risposta!
Infatti avevo già provato quella scomposizione, generalizzando ho preso $a^t b^n c^(n-1)$.
Comunque se prendo abbc e di questa prendo la scomposizione $u=\varepsilon (vuota), v=a, w= b b c$ allora il pompaggio porta ancora ad una stringa del linguaggio! Com'è possibile? La proprietà $|uv| <= n $ è verificata (n=2). Dove sbaglio?

EDIT: Grande Fail. La scomposizione $u=\varepsilon, v=a, w= b b c$ non verifica il PL. Spompando v ottengo bbc che non appartiene al linguaggio. Mi ero dimenticato che le a, le b e le c sono obbligate ad esserci.

Cita

Segnala

---

MenoInfinito

17 mag 2013, 09:47

Mi sembra che con ogni scomposizione possibile (Ricordando sempre che $v \ne \epsilon$) ottieni delle stringhe non appartenenti al linguaggio.
Per cui il pumping lemma non è valido.
E quindi il linguaggio non è regolare.

Cita

Segnala

---

abbobba1

3 apr 2014, 15:54

Io ho risoltò così:

scelgo $ z = a^(n/2) b^(n/2) c^(n/2-1) $

quindi pongo $v = b^h$ con h>0
risulterà
$z = a^(n/2) b^(n/2-h) (b^h)^i c^(n/2-1)$ ponendo i = 0

$z = a^(n/2) b^(n/2-h) c^(n/2-1)$ che non appartiene a L

giusto?

mentre se avessi scelto i > 0 gonfiando la stringa salta la condizione |uv|<=n e quindi non appartiene a L è corretto?

Cita

Segnala

---

Rispondi

Per rispondere a questa discussione devi prima effettuare il login.

[MenoInfinito]

Devi trovare una stringa che possa essere un valido controesempio e che in qualunque modo venga decomposta dia luogo, col pompaggio, ad una stringa non appartenente al linguaggio.

Di primo acchito... se prendi z = abbc dovresti aver trovato una stringa appartente al L ma che in qualunque modo venga decomposta non apparterra', post pompaggio, ad L (Per i = 0).
Dai un'occhiata.

[pier_IP]

Ciao grazie della risposta!
Infatti avevo già provato quella scomposizione, generalizzando ho preso $a^t b^n c^(n-1)$.
Comunque se prendo abbc e di questa prendo la scomposizione $u=\varepsilon (vuota), v=a, w= b b c$ allora il pompaggio porta ancora ad una stringa del linguaggio! Com'è possibile? La proprietà $|uv| <= n $ è verificata (n=2). Dove sbaglio?

EDIT: Grande Fail. La scomposizione $u=\varepsilon, v=a, w= b b c$ non verifica il PL. Spompando v ottengo bbc che non appartiene al linguaggio. Mi ero dimenticato che le a, le b e le c sono obbligate ad esserci.

[MenoInfinito]

Mi sembra che con ogni scomposizione possibile (Ricordando sempre che $v \ne \epsilon$) ottieni delle stringhe non appartenenti al linguaggio.
Per cui il pumping lemma non è valido.
E quindi il linguaggio non è regolare.

[abbobba1]

Io ho risoltò così:

scelgo $ z = a^(n/2) b^(n/2) c^(n/2-1) $

quindi pongo $v = b^h$ con h>0
risulterà
$z = a^(n/2) b^(n/2-h) (b^h)^i c^(n/2-1)$ ponendo i = 0

$z = a^(n/2) b^(n/2-h) c^(n/2-1)$ che non appartiene a L

giusto?

mentre se avessi scelto i > 0 gonfiando la stringa salta la condizione |uv|<=n e quindi non appartiene a L è corretto?