[INFORMATICA TEORICA] ESERCIZIO PUMPING LEMMA

[starbike]

Devo dimostrare che il seguente linguaggio non è regolare :

L={ww | w appartiene a {0,1}* } dove w e la stringa w invertendo gli 0 con gli 1.
Qualcuno mi potrebbe aiutare?

[vict85]

Si prega di usare le formule. Così è difficile comprendere il testo.

[ramy1989]

Ci provo:
Un esempio di stringa può essere z=01011010
La divido in u=010 , v=110, w=10
Per k=2 \(uv^2w\) = 01011011010 \( \in L\)
Quindi non è regolare (correggetemi se ho sbagliato qualcosa).

[starbike]

"ramy1989":Ci provo:
Un esempio di stringa può essere z=01011010
La divido in u=010 , v=110, w=10
Per k=2 \(uv^2w\) = 01011011010 \( \in L\)
Quindi non è regolare (correggetemi se ho sbagliato qualcosa).

no no il ragionamento e giusto è che la spiegazione va fatta in generale prendendo s=0^k1^k ma nn sn sicura

[Deckard1]

"ramy1989":Ci provo:
Un esempio di stringa può essere z=01011010
La divido in u=010 , v=110, w=10
Per k=2 \(uv^2w\) = 01011011010 \( \in L\)
Quindi non è regolare (correggetemi se ho sbagliato qualcosa).

Non puoi applicare il pumping lemma in questo modo: il pumping lemma vale solo per stringhe con lunghezza maggiore di un certo $p$. Ma questo $p$ può essere 10, 20, 2^100. Devi astrarre il tuo ragionamento, non puoi usare una stringa particolare del linguaggio, devi perlomeno utilizzare una stringa la cui lunghezza dipenderà in qualche modo da $p$.

[ramy1989]

E questo p come si calcola?

[Deckard1]

Non lo devi calcolare. Devi fare la dimostrazione qualunque valore sia questo $p$. Rileggiti attentamente l'enunciato del pumping lemma per i linguaggi regolari e vedrai che la cosa ti sarà più chiara.

[ramy1989]

Prendiamo p=4 , z=0110 , |z|\(\ge\)p perchè |z|=4, z\(\in\)L.
Prendo u=01, v=1, w=0 .
1)E' valido che |uv|\(\le\)p ;
2)E' valido che |v|\(\ge\) 1;
3)Prendo ad esempio k=2, uv\(^2\)w = 01110 \(\notin\)L .

[Deckard1]

No. Non puoi fissare il valore di $p$. Ripeto, rileggiti l'enunciato e vedrai che quello stai facendo non è applicare il pumping lemma.