| V I S U A L I Z Z A D I S C U S S I O N E |
| xgeneralex |
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 ?
 |
| 5 U L T I M E R I S P O S T E (in alto le più recenti) |
| Piplos |
Inserito il - 26/06/2011 : 11:51:55
Grazie mago, mi hai aiutato a capire meglio il procedimento :) |
| mago |
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. |
| mago |
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.
|
| xgeneralex |
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  |
| mago |
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. |
