| V I S U A L I Z Z A D I S C U S S I O N E |
| ianus |
Inserito il - 18/04/2006 : 12:04:21
Mi scuso per aver aperto un nuovo topic, ma essendo l'appello di aprile alle porte ed essendomi rimasti grazie al cielo pochi interrogativi volevo chiedere come risolvere i seguenti esercizi, se non altro per avere un metro di paragone
26 gennaio 2006 , appello del prof lops. esercizio 1
dato il seguente linguaggio
L= a^j b^k c^k: 0 <= j <= k
-dimostrare formalmente che L non è l.d.
-stabilire se è CF
penso si potrebbe dimostrare correttamente con le proprietà di chiusura
2 maggio 2002 esercizio 1
stabilire se il seguente linguagio a^m b^n c^k : m = n, k > 0 è cf... fondamentalmente questo è molto simile, direi quasi uguale al precedente, anche come modalità di risoluzione
11 febbraio 2003
stabilire se a^i b^k c^j , k = i+j, i,j,k>0 è cf
quest'ultimo esercizio provo a dimostrarlo con il pumping lemma per i linguaggi cf considerando la parole a^p b^2p c^p appartenente a L, ma quando arrivo al quarto caso ovvero considero vx = a^r b^s
ottengo
a^(p+r) b^(2p+s) c^p ... ma se r=s la parola z appartiene al linguaggio, perciò cosa ne dovrei dedurre? che il linguaggio è cf?
Spero in una risposta prima di venerdì, ringrazio per l'attenzione
a^p+r b^2p |
| 19 U L T I M E R I S P O S T E (in alto le più recenti) |
| ianus |
Inserito il - 20/04/2006 : 15:16:34
voi come dimostrereste che
a^i b^j c^k : k = i + j i,j,k>=0
è o non è context free ? |
| ianus |
Inserito il - 20/04/2006 : 09:02:28
allora credo di aver risolto col pumping lemma per i linguaggi cf
dato il seguente linguaggio
L= a^j b^k c^k: 0 <= j <= k
stabilire che è cf(stabilire se è lineare destro si capisce facilmente con il pumpin lemma per i linuaggi regolari, basta pompare infatti a, considerando magari una parola a^p b^p c^p appartenente al linguaggio per vedere che essa non soddisfapiù j<=k)
allora per il pumpig lemma credo che l'arcano si sveli depompando la stringa
consideriamo la parola
a^p b^p c^p
i primi casi si risolvono facilmente con la stringa
u v^2 w x^2 y
infatti abbiamo i 4 casi
vwx formata da
tutte a: ovvero abbiamo a^k+p k+p>p
tutte b: ovvero abbiamo b^k+p , ma il numero di c è rimasto p, perciò p != p+k, la stringa non appartiene al linguaggio
tutte c: ovvero vedi caso precedente
a e b: si rifà al primo caso, abbiamo a^r+p b^s+p, ma r+p non sappiamo se è minore di s+, ma sicuramente è minore di p dato che le c sono rimaste uguali
il problema viene per vwx composta da b e c ma l'ho risolto così
considero per questo caso la stringa depompata u v^0 w x^0 y
per vwx stabiliamo i soliti r ed s tali che r+s<=p invece di sommare sottraiamo gli esponenti ottenendo così
a^p b^p-r c^p-s che chiaramente non appartiene al linguaggio perchè viola i vincoli su a e b, fatemi sapere se la cosa vi convince
|
| ianus |
Inserito il - 19/04/2006 : 19:04:44
bene chilavert, mi hai fatto vincere una scommessa riguardo l'automa, ci avevo visto giusto, però stiamo ancora impazzendo su quel famoso dubbio di cui sopra al primo post, primo esercizio, nessuna idea ragazzi? cmq chilavert sei un idolo soprattutto per il tuo avatar, grazie ancora |
| Chilavert |
Inserito il - 19/04/2006 : 16:53:04
Sì, lo è
Perché? perché con un automa a 5 stati lo risolvi faclimente (un automa che torna allo stato iniziale dopo 5 salti, cerca di capire com'è perché non mi va di disegnarlo  )
Comunque nella sezione download mi sa che fra gli automi risolti da me ci sta pure questo qui... |
| ianus |
Inserito il - 19/04/2006 : 15:37:49
pongo qui un dubbio amletico al centro di una discussione fra esaminandi
L = w appartiene ad (a,b)* : |w| = 5k, k>= 0
è un linguaggio context free? e se si, perchè? |
| ianus |
Inserito il - 19/04/2006 : 11:29:52
ho provato a rifarmi all'esercizio 5.4 del semeraro ma nulla, eppure ci deve essere un modo |
| Marketto |
Inserito il - 19/04/2006 : 10:55:14
Vero...grazie mille!!!! |
| genius |
Inserito il - 19/04/2006 : 10:52:06
Citazione:
Messaggio inserito da Marketto
Solo S -> bSc | lambda ???
Non manca qualcosa??
no, queste sono sufficenti...
per quanto riguarda j < k in effetti qualke problema potrebbe sorgere...
mhm... |
| ianus |
Inserito il - 19/04/2006 : 10:52:06
credo di no rimane il fatto che concatenare
a^j
e
b^k c^k
non dà la certezza che la relazione j<k venga mantenuta
ho riprovato col pumping lemma ma niente, il problema è sempre sulle stringhe a cavallo, bisogna trovare un modo per ridurre il linguaggio a concatenazione o unione (forse più la seconda) o magari intersezione o colplemeto di altri linguaggi |
| Marketto |
Inserito il - 19/04/2006 : 10:48:37
Solo S -> bSc | lambda ???
Non manca qualcosa?? |
| ianus |
Inserito il - 19/04/2006 : 10:30:40
giusto genius, avevo pensato lo stesso anchio come avevo scritto sopra, quello che non mi convince è la relazione j<=k, se non ci fosse stata direi molto più a cuor leggero che trattasi di una concatenazione, tu pensi che mi preoccupo troppo per nulla? ;)
ad esempio io agirei così nel secondo esercizio riportato nel primo post
a^m b^n c^k : m=n ,k>0 non essendovi alcun legame fra a^m b^n e c^k, L è semplice concatenazione
Per marco
penso che le produzioni che cerchi siano
S>bSc | lambda |
| Marketto |
Inserito il - 19/04/2006 : 10:29:45
Ok, per esperienza..effettivamente era l'operazione più logica...Ma le produzioni di L2 (ovvero di b^k c^k) quali sono?
Io ho pensato: {S -> bc | bBcC | lambda
B -> bB | b
C -> cC | c}
Non credo però siano corrette...
Grazie ancora... |
| genius |
Inserito il - 19/04/2006 : 10:26:33
perkè qui si nota ke il linguaggio è composto da a^j concatenato b^k c^k... non c'è un criterio sempre vero, è come per gli integrali, molto fa l'esperienza... |
| Marketto |
Inserito il - 19/04/2006 : 10:22:48
Citazione:
infatti sarebbe una cocatenazione di a^j e b^k c^k
In base a cosa si capisce se utilizzare la concatenazione piuttosto che l'unione? |
| ianus |
Inserito il - 19/04/2006 : 10:13:15
ciao chilavert, riguardo al primo post che avevo scritto, volevo sapere come risolvere gli esercizi, riguardo al primo avevo una mezza idea basandomi sulle proprietà di chiusura
dato il seguente linguaggio
L= a^j b^k c^k: 0 <= j <= k
-dimostrare formalmente che L non è l.d.
-stabilire se è CF
infatti sarebbe una cocatenazione di a^j e b^k c^k cioè di un lineare dx e di un cf, pertanto L sarebbe un cf ma nn ld. essendovi però la relazione fra j e k sarebbe meglio applicare il pumping lemma per i linguaggi cf e il pumping lemma per i linguaggi regolari.
Riguardo agli altri due esercizi sono riuscito a togliermi parecchi dubbi, rimane quest'ultimo, ti ringrazio chilavert per la pazienza |
| Chilavert |
Inserito il - 19/04/2006 : 09:29:01
Cosa vuoi sapere precisamente? |
| ianus |
Inserito il - 18/04/2006 : 18:20:11
hai ragionissima chilavert, l'ho letto il teorema, era solo che riguardo gli esercizi non mi sentivo sicuro lo stesso.
Meno male mi hai levato un dubbio, pensavo di aver sbagliato tutti gli esercizi fino ad oggi :D
grazie ancora
riguardo al primo post? non mi sai dare nessuna  zione? |
| Chilavert |
Inserito il - 18/04/2006 : 17:38:43
Esiste anche un teorema che sostiene che è possibile emulare con un automa deterministico uno stesso automa, però non deterministico.
Quindi... |
| ianus |
Inserito il - 18/04/2006 : 17:35:49
salve sono sempre io, volevo chiedere un 'altra cosa riguardo al teorema di kleene.
Quando ci si riferisce ad "automa a stati finiti" è indifferente che tale automa sia deterministico o nondeterministico?
Credo di sì ma gradirei una precisazione se fosse possibile, ringrazio per la pazienza e mi scuso nuovamente per il disturbo |
