Pages: [1]   Go Down
Print
Author Topic: Pumping Lemma per esercizio 30  (Read 103 times)
0 Members e 1 Utente non registrato stanno visualizzando questa discussione.
Dott.V
Matricola
*
Offline Offline

Posts: 36


« on: 12-09-2017, 12:08:19 »

Buongiorno a tutti. Vi propongo la mia soluzione di un esercizio preso dal sito del prof. Barbanera.

L={a^k b^n c^m | n ≥0, k≤ n, n≤ m}  è regolare?

Informalmente posso dire che non c'è modo per l'automa di verificare che la relazione 0<=k<=n<=m sia verificata, in quanto l' ASFD potrebbe riconoscere stringhe in cui il numero di a sia superiore al numero di b ma che ovviamente non appartengono al nostro L.

Attraverso le condizioni che ci offre il PL affinchè un L sia regolare possiamo verificare la correttezza dell'affermazione precedente.

Se L fosse regolare allora esisterebbe una costante c tale che una qualunque stringa s di L, con |s|>=c, potrebbe essere spezzata in s=uvw rispettando le sequenti condizioni:
- s=uv^iw appartenente ad L per ogni i>=0
-|v|>0
-|uv|<=c

Ipotesi: L è regolare.
Tesi: secondo il PL possiamo suddividere una stringa s di L in s=uvw ,|s|>=c.

Consideriamo le stringhe :
-str1=uv di sole 'a'; lunghezza c;
-str2=w di 'b' e 'c'; lunghezza 2c; stesso numero di 'b' e stesso numero di 'c'.

La nostra stringa sarebbe str=str1*str2 - > str=a^c b^c c^c

Secondo il PL la str=uv^iw è appartenente ad L per ogni i>=0;
siccome sappiamo che v=a in quanto str1 contiene solo 'a' ed |v|>0, qualunque stringa str=a^(c+i)b^c c^c non appartiene ad L se i>0, perchè avremmo un numero superiore di 'a' rispetto al numero di 'b' e di 'c'.
Pur non essendo una stringa appartenente ad L l'automa si porterà in uno stato di accettazione in quanto attraverserà lo stato in cui legge le sole 'a' non potendo verificare successivamente se sia inferiore al numero di 'b' e di 'c'.
Spero che la dimostrazione formale sia sufficientemente esaustiva.
Cordiali saluti.


Logged
Franco Barbanera
Moderator
Forumista Eroico
*****
Offline Offline

Posts: 2.622



WWW
« Reply #1 on: 13-09-2017, 16:35:31 »

Quote
Consideriamo le stringhe :
-str1=uv di sole 'a'; lunghezza c;
-str2=w di 'b' e 'c'; lunghezza 2c; stesso numero di 'b' e stesso numero di 'c'.

Tu sai solo che s si puo' suddividere in sottostringhe,
ma non puoi decidere tu come sono fatte u, v e w ....

Puoi invece dire: prendiamo una stringa di lunghezza maggiore di c, che sia
del linguaggio e della forma ....

FB
Logged
Dott.V
Matricola
*
Offline Offline

Posts: 36


« Reply #2 on: 14-09-2017, 09:54:26 »

Quote
Consideriamo le stringhe :
-str1=uv di sole 'a'; lunghezza c;
-str2=w di 'b' e 'c'; lunghezza 2c; stesso numero di 'b' e stesso numero di 'c'.

Tu sai solo che s si puo' suddividere in sottostringhe,
ma non puoi decidere tu come sono fatte u, v e w ....

Puoi invece dire: prendiamo una stringa di lunghezza maggiore di c, che sia
del linguaggio e della forma ....

FB
Grazie della risposta. Posso dire quindi che
- str1=uv che contiene solo 'a'
-str2=w che contiene sia 'a' che 'b'

senza che possa intervenire sulla vera e propria forma della stringa?
Logged
Franco Barbanera
Moderator
Forumista Eroico
*****
Offline Offline

Posts: 2.622



WWW
« Reply #3 on: 17-09-2017, 16:34:28 »

No, puoi solo dare una stringa del linguaggio.
Devi ottenere una contraddizione indipendentemente da come sara' scomposta la stringa in uvw.

FB
Logged
Pages: [1]   Go Up
Print
Jump to: