| Autore |
 Discussione  |
|
|
xgeneralex
Utente giovane
Regione: Puglia
Prov.: Bari
Città: Bari
|
 Inserito il - 12/11/2010 : 18:43:58
|
1)Dimostrare formalmente che il seguente linguaggio:
L = {a^n b^k c^n : | n > 0, k > n}
non è libero da contesto
come faccio ad operare in base alle sole a alle sole b o alle c e poi gli altri due casi?
io proprio non riesco a capire bene come fare ad applicare il PL in questi casi...c'è un modo per capirlo una volta per tutte?
C'è qualcuno che mi aiuta ?
|
..siamo solo noi...generazione di sconvolti ke nn han + santi nè eroi...siamo solo noiiiiiiiiiiiiiiiiiii.... |
|
|
mago
Utente giovane
|
Inserito il - 13/11/2010 : 10:31:45
|
| Devi distinguere i casi in cui vwx è formata da sole a oppure sole b oppure sole c oppure può essere a cavallo tra a e b e tra b e c. Poi consideri la stringa pompata per i casi elencati (ad esempio uv^2wx^2y). Primo caso esempio se aggiungiamo una a ed al più p a uv^2wx^2y non appartiene al linguaggio. |
 |
|
|
xgeneralex
Utente giovane
Regione: Puglia
Prov.: Bari
Città: Bari
|
Inserito il - 13/11/2010 : 11:23:01
|
mago innanzitutto grazie per la risposta, potresti essere più preciso scrivendomi un esempio tipo esercizio? e magari anche l'esempio 4 a cavallo tra a e b quando v o x diverso da lamba.
inoltre vorrei capire appunto come operare in base alle lettere, n>0 k>n...è il dubbio che mi attanaglia ad ogni risoluzione di pumping lemma. in modo tale che se ne capisco uno li capisco tutti... Grazie  |
..siamo solo noi...generazione di sconvolti ke nn han + santi nè eroi...siamo solo noiiiiiiiiiiiiiiiiiii.... |
Modificato da - xgeneralex in data 13/11/2010 11:26:38 |
|
|
|
mago
Utente giovane
|
Inserito il - 15/11/2010 : 12:06:09
|
Per L={a^ib^jc^k, k=max(i,j), i,j,k>0} se considero z=a^pb^pc^p suddivido i casi per |vwx| (dato che vwx ha lunghezza al più uguale a p)
1. vwx formata da sole a esempio vwx=a^k, 0<k<=p
...
4. vwx è a cavallo tra a e b esempio vwx=a^kb^r, 0<k+r<=p, k,r>0
...
Consideri la stringa pompata uv^2wx^2y per ogni caso sopra.
1. aggiungiamo almeno una a ed al più p a esempio uv^2wx^2y=a^(p+t)b^pc^p, 0<t<=p uv^2wx^2y non appartiene ad L poichè il numero di a >numero di c
...
4. distingui i casi in cui vdiversolambda e xdiverso lambda, vdiversolambda e x=lambda, v=lambda e xdiversolambda.
|
|
|
|
mago
Utente giovane
|
Inserito il - 15/11/2010 : 12:10:29
|
4. vdiversolambda x=lambda
v=a^y', 0<y'<=y
uv^2wx^2y=a^(p+y')b^pc^p non appartiene ad L perchè y'>0 e il numero di a > numero di c. |
|
|
|
Piplos
Nuovo Utente
|
Inserito il - 26/06/2011 : 11:51:55
|
| Grazie mago, mi hai aiutato a capire meglio il procedimento :) |
|
|
| |
Discussione |
|
mi aiutate a svelare un pompaggio
