| Autore |
 Discussione  |
|
|
ianus
Nuovo Utente
|
 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
|
|
|
ianus
Nuovo Utente
|
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 |
 |
|
|
Chilavert
admin
Regione: Puglia
Prov.: BA
Città: Bari
|
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... |
E' un bene per il Prof. Xxxxxxx che sappia con chi ha a che fare.
Pensa a studiare e non agli esempi, o ad altre strade per così dire,
che questa volta mi sa che non attacca. [cit.]
Tutti professori dall'esterno, e poi parlano persone che per prendere un voto decente
ripetono l'esame 30 volte e poi fanno i sapientoni con chi segue la prima volta vedi chilavert [cit.] |
|
|
|
ianus
Nuovo Utente
|
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
admin
Regione: Puglia
Prov.: BA
Città: Bari
|
Inserito il - 19/04/2006 : 09:29:01
|
| Cosa vuoi sapere precisamente? |
E' un bene per il Prof. Xxxxxxx che sappia con chi ha a che fare.
Pensa a studiare e non agli esempi, o ad altre strade per così dire,
che questa volta mi sa che non attacca. [cit.]
Tutti professori dall'esterno, e poi parlano persone che per prendere un voto decente
ripetono l'esame 30 volte e poi fanno i sapientoni con chi segue la prima volta vedi chilavert [cit.] |
|
|
|
ianus
Nuovo Utente
|
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 |
|
|
|
Marketto
Utente medio
Regione: Puglia
Prov.: Ba
Città: Bari
|
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? |
Marco
Visitate il mio blog: http://www.cambridgetime.splinder.com |
|
|
|
genius
dott. ing. cav. ...FN
Regione: Puglia
Prov.: Bari
Città: Molfetta - Caput Mundi
|
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... |
"...e se non hai morale
e se non hai passione
se nessun dubbio ti assale
perché la sola ragione che ti interessa avere
è una ragione sociale
soprattutto se hai qualche dannata guerra da fare
non farla nel mio nome
non farla nel mio nome
che non hai mai domandato la mia autorizzazione
se ti difenderai non farlo nel mio nome
che non hai mai domandato la mia opinione..."
Un blog farlocco |
|
|
|
Marketto
Utente medio
Regione: Puglia
Prov.: Ba
Città: Bari
|
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... |
Marco
Visitate il mio blog: http://www.cambridgetime.splinder.com |
Modificato da - Marketto in data |
|
|
|
ianus
Nuovo Utente
|
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 |
Modificato da - ianus in data |
|
|
|
Marketto
Utente medio
Regione: Puglia
Prov.: Ba
Città: Bari
|
|
|
genius
dott. ing. cav. ...FN
Regione: Puglia
Prov.: Bari
Città: Molfetta - Caput Mundi
|
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... |
"...e se non hai morale
e se non hai passione
se nessun dubbio ti assale
perché la sola ragione che ti interessa avere
è una ragione sociale
soprattutto se hai qualche dannata guerra da fare
non farla nel mio nome
non farla nel mio nome
che non hai mai domandato la mia autorizzazione
se ti difenderai non farlo nel mio nome
che non hai mai domandato la mia opinione..."
Un blog farlocco |
|
|
|
ianus
Nuovo Utente
|
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 |
Modificato da - ianus in data |
|
|
|
Marketto
Utente medio
Regione: Puglia
Prov.: Ba
Città: Bari
|
|
|
ianus
Nuovo Utente
|
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 |
|
|
|
ianus
Nuovo Utente
|
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è? |
|
|
|
Chilavert
admin
Regione: Puglia
Prov.: BA
Città: Bari
|
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... |
E' un bene per il Prof. Xxxxxxx che sappia con chi ha a che fare.
Pensa a studiare e non agli esempi, o ad altre strade per così dire,
che questa volta mi sa che non attacca. [cit.]
Tutti professori dall'esterno, e poi parlano persone che per prendere un voto decente
ripetono l'esame 30 volte e poi fanno i sapientoni con chi segue la prima volta vedi chilavert [cit.] |
|
|
|
ianus
Nuovo Utente
|
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 |
|
|
|
ianus
Nuovo Utente
|
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
Nuovo Utente
|
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 ? |
|
|
| |
Discussione |
|
dubbi amletici
