Pages: [1]   Go Down
Print
Author Topic: Dubbio Pumping Lemma  (Read 538 times)
0 Members e 1 Utente non registrato stanno visualizzando questa discussione.
jeremy_sapienza
Matricola
*
Offline Offline

Posts: 11


« on: 13-01-2018, 18:38:11 »

salve prof, facendo un esercizio sul pumping lemma, mi è sorto un dubbio...spero comunque che chiunque mi possa rispondere.

Fissato un numero k qualsiasi, il seguente linguaggio e' regolare?
{a^k b^n c^m | n>=0, k<=n, n<=m}

provando a fissare un k qualsiasi il linguaggio mi sembra che sia regolare..

però comunque ho voluto verificare tale veriticità, visto che il pumping funziona con i linguaggi regolari ed infatti... no Pumping -> no regolare.

comunque, dalle premesse del teorema ... trovo una stringa:
z = a^f b^f+1 c^f+2 appartenente al linguaggio..

si ha quindi |uv| <=f e |v|>=1, nel nostro caso: |a^f b^f|<=f   |b^f|>=1

se pongo la nostra v^i con i = 3, il numero di v sarebbe più grande di c e quindi non sarebbe più appartenente al linguaggio, in sostanza è un assurdo..

i miei dubbi quindi sono...
1)la mia v corrisponde esattamente a b^f? quindi se i=3, sarebbe in sostanza a^f b^f 3b^f c^f+2..?
2)trovando con il pumping questa irregolarità... com'è possibile che fissando un k qualsiasi, riesco a trovare sempre una stringa che appartiene al linguaggio...?

sono un pò confuso, quindi nel caso stia dicendo delle assurdità, perdonatemi  pray (anche perchè con stringhe di tipo a^n b^m, non ho avuto problemi)
Logged
Franco Barbanera
Moderator
Forumista Eroico
*****
Offline Offline

Posts: 2.918



WWW
« Reply #1 on: 14-01-2018, 17:24:38 »

provando a fissare un k qualsiasi il linguaggio mi sembra che sia regolare..

Se la tua intuizione e' che sia regolare, allora dovresti provare a trovare un automa che riconosca il linguaggio
oppure una espressione regolare che lo rappresenti.

Tieni presente pero' che un automa che riconoscesse il linguaggio,
in un certo senso dovrebbe "saper contare". Infatti dovrebbe capire che il numero di c e'
maggiore del numero di b.
Parrebbe quindi non regolare.

Nel tuo discorso tu inizi dicendo

"trovo una stringa:
z = a^f b^f+1 c^f+2 appartenente al linguaggio.."

Cosa e' f?
Dovresti dire: fisso un f e considero il linguaggioù
a^f b^n c^m | n>=0, k<=n, n<=m}
A questo punto assumi che per questo linguaggio valga il Pumping Lemma.

Poi continui dicendo
"si ha quindi |uv| <=f e |v|>=1, nel nostro caso: |a^f b^f|<=f   |b^f|>=1"

Perche' dici si ha quindi |uv| <=f e |v|>=1 ?

Non puoi dirlo.
Logged
jeremy_sapienza
Matricola
*
Offline Offline

Posts: 11


« Reply #2 on: 15-01-2018, 12:43:48 »

provando a fissare un k qualsiasi il linguaggio mi sembra che sia regolare..

Se la tua intuizione e' che sia regolare, allora dovresti provare a trovare un automa che riconosca il linguaggio
oppure una espressione regolare che lo rappresenti.

Tieni presente pero' che un automa che riconoscesse il linguaggio,
in un certo senso dovrebbe "saper contare". Infatti dovrebbe capire che il numero di c e'
maggiore del numero di b.
Parrebbe quindi non regolare.

Nel tuo discorso tu inizi dicendo

"trovo una stringa:
z = a^f b^f+1 c^f+2 appartenente al linguaggio.."

Cosa e' f?
Dovresti dire: fisso un f e considero il linguaggioù
a^f b^n c^m | n>=0, k<=n, n<=m}
A questo punto assumi che per questo linguaggio valga il Pumping Lemma.

Poi continui dicendo
"si ha quindi |uv| <=f e |v|>=1, nel nostro caso: |a^f b^f|<=f   |b^f|>=1"

Perche' dici si ha quindi |uv| <=f e |v|>=1 ?

Non puoi dirlo.


ok, prof mi sono documentato per la rete ed ho avuto qualche chiarezza...
la mia f sarebbe la costante che io sto introducendo, per dimostrare la validità del pumping lemma.
Dopo trovo una stringa z che appartiene al linguaggio L, in quel caso ho scelto quel tipo di stringa sottostando ai vincoli scritti... non sto capendo perchè quella costante l'ha attribuita solamente alla a...io vedendo l'esercizio noto che basta aumentare il numero di b rispetto alla c, per rendere una qualsiasi stringa non regolare.. in sostanza, la mia costante f non la posso attribuire in quel modo?
Logged
Franco Barbanera
Moderator
Forumista Eroico
*****
Offline Offline

Posts: 2.918



WWW
« Reply #3 on: 15-01-2018, 13:20:08 »

la mia f sarebbe la costante che io sto introducendo, per dimostrare la validità del pumping lemma.

Se intendi dire che la f e' la costante la cui esistenza e' garantita dal Pumping Lemma,
stai ragionando in modo scorretto.

Noi partiamo dall'affermazione (probabilmente errata) che, preso un numero k,
il linguaggio  Lk, definito come
Lk = {a^k b^n c^m | n>=0, k<=n, n<=m},
e' regolare.
Per il Pumping lemma quindi dovrebbe esistere una costante c (quella che tu chiami f, immagino) tale che... ecc. ecc.
Nota che la  costante c dipende dal linguaggio Lk, e quindi da k.
Non puoi pensare (come credo tu abbia fatto) che la costante c sia unica per tutti i possibili linguaggi Lk...

Logged
jeremy_sapienza
Matricola
*
Offline Offline

Posts: 11


« Reply #4 on: 15-01-2018, 17:42:23 »

la mia f sarebbe la costante che io sto introducendo, per dimostrare la validità del pumping lemma.

Se intendi dire che la f e' la costante la cui esistenza e' garantita dal Pumping Lemma,
stai ragionando in modo scorretto.

Noi partiamo dall'affermazione (probabilmente errata) che, preso un numero k,
il linguaggio  Lk, definito come
Lk = {a^k b^n c^m | n>=0, k<=n, n<=m},
e' regolare.
Per il Pumping lemma quindi dovrebbe esistere una costante c (quella che tu chiami f, immagino) tale che... ecc. ecc.
Nota che la  costante c dipende dal linguaggio Lk, e quindi da k.
Non puoi pensare (come credo tu abbia fatto) che la costante c sia unica per tutti i possibili linguaggi Lk...



ok, ho ragionato in maniera errata per questa tipologia di esercizio... ma quindi non c'è nulla da prendere dalla mia dimostrazione..? in sostanza la stringa che ho è corrispondente a: a^f b^n c^m? dovrei quindi eseguire il tutto, trovando una i che mi rende la stringa non appartenente al linguaggio.. seguendo questa: a^f b^n c^m? sinceramente mi trovo un pò spiazzato 
Logged
Franco Barbanera
Moderator
Forumista Eroico
*****
Offline Offline

Posts: 2.918



WWW
« Reply #5 on: 15-01-2018, 21:19:39 »


Prendi un k e consideri il linguaggio Lk.

A questo punto se Lk e' regolare esistera' una costante c tale che,
ogni z con |z|>= c si puo' suddividere in uvw tali che ecc.ecc.

Devi prendere un opportuno z in modo da arrivare ad una contraddizione
Logged
jeremy_sapienza
Matricola
*
Offline Offline

Posts: 11


« Reply #6 on: 18-01-2018, 09:09:35 »


Prendi un k e consideri il linguaggio Lk.

A questo punto se Lk e' regolare esistera' una costante c tale che,
ogni z con |z|>= c si puo' suddividere in uvw tali che ecc.ecc.

Devi prendere un opportuno z in modo da arrivare ad una contraddizione

la soluzione è la seguente..
avendo un fissato k, noi dobbiamo trovare una determinata costante c (potevo dare un qualsiasi nome) che dipenda anche dal valore di k. Nel linguaggio Lk = {a^k b^n c^m | n>=0, k<=n, n<=m} dobbiamo fornire le nostre premesse del pumping lemma:

presa una qualsiasi costante f con |z|>=f
esiste una stringa z=uvw con |uv|<=f e |v|>=1
esisterà quindi uv^iw appartenente al linguaggio, qualunque sia la nostra i>=0

a questo punto ci tocca trovare questa nostra stringa che essendo dipendente anche dal valore fissato da k, diventa ad esempio:

a^k b^k+f c^k+f+1

supponiamo a questo punto di assegnare a:
u = a^k b^k
v = b^f
w = la parte rimanente, ovvero, c^k+f+1

a questo punto dobbiamo trovare una determinata i che mi renda la mia stringa non appartenente al linguaggio Lk.

supposto che io assegni ad i il valore di 2, avremo una stringa in cui la nostra b è superiore al numero di c, ciò va in contraddizione con il nostro linguaggio Lk

quindi non è appartenente al linguaggio.

se ci sono errori riperdonatemi  pray







 
« Last Edit: 18-01-2018, 18:07:16 by jeremy_sapienza » Logged
Franco Barbanera
Moderator
Forumista Eroico
*****
Offline Offline

Posts: 2.918



WWW
« Reply #7 on: 18-01-2018, 22:39:11 »

Quote
avendo un fissato k, noi dobbiamo trovare una determinata costante c

No. Non devi "trovarla". Sai che esiste una costante con certe proprieta'. E puoi chiamarla c (o pippo o fifi').

Il seguito contiene poi inprecisioni. Rileggiti bene cosa afferma il Pumping Lemma.
Logged
Pages: [1]   Go Up
Print
Jump to: