| Autore |
 Discussione  |
|
|
roccodigit
Nuovo Utente
Città: Palazzo S.G.
|
 Inserito il - 18/06/2011 : 12:41:23
|
Qualcuno si ricorda precisamente la traccia dell'appello del 10 giugno??
mi interesserebbe soprattutto il terzo esercizio!!
|
|
|
Marsigliese
Utente giovane
Città: Bari
|
Inserito il - 19/06/2011 : 12:17:47
|
da cio' che ricordo dovrebbe essere questo o qualcosa simile:
dato il linguaggio: L = {a3bn : n>0}
-Determinare la classe L nella gerarchia di Chomsky.
-Definire una grammatica generativa corretta per L.
-Descrivere formalmente il linguaggio X* - L, dove X = {a,b}.
|
 |
|
|
roccodigit
Nuovo Utente
Città: Palazzo S.G.
|
Inserito il - 19/06/2011 : 20:22:16
|
| Si grazie, dovrebbe essere cosi ;) |
|
|
|
Piplos
Nuovo Utente
|
Inserito il - 26/06/2011 : 11:30:08
|
Visto che ci siamo possiamo scrivere anche le soluzioni?
Per la 1 e la 2 credo di saper rispondere io (correggetemi se sbaglio):
1) Il linguaggio è di tipo 3 nella gerarchia di Chomsky, visto che nella grammatica definita in seguito possiamo osservare che è lineare destra.
2) Definizione di grammatica:
S-->aaabB
B-->b|lambda
Per la terza non so come rispondere, qualcuno sa aiutarmi? |
|
|
|
Premoli
Utente giovane
|
Inserito il - 26/06/2011 : 11:53:30
|
Ciao!!!
Per la terza bastava notare, che X*-L è uguale a X*(intersecato)^L (^L = al complemento di L)
quindi per farlo potevi trovare l'automa che genera il linguaggio L e successivamente complementarlo, per quello al punto 2 ti conveniva trovare già una grammatica lineare destra così la costruzione dell'automa era immediata, ricorda che per complementare l'automa la funzione di transizione (delta) deve essere totale.
una grammatica lineare destra per generare L può essere:
S>aA
A>aB
B>aC
C>b|bB |
|
|
|
Piplos
Nuovo Utente
|
Inserito il - 26/06/2011 : 12:11:31
|
Perfetto, mi sono completamente bloccato :D
Credevo che bastasse semplicemente dire che X*-L è un linguaggio formato da stringhe che non iniziano per aaab.
By the way, so come fare l'automa, ma non so come complementarlo. C'è scritto da qualche parte negli appunti di teoria dei linguaggi formali (del prof. semeraro)?
Altra cosa, ma la grammatica generativa che ho scritto io andava bene? o bisogna per forza avere un solo simbolo terminale nella parte destra di ogni produzione? |
|
|
|
Piplos
Nuovo Utente
|
Inserito il - 26/06/2011 : 12:12:51
|
| Scusa, ho visto solo ora, bisogna per forza avere un solo simbolo terminale. Quindi la grammatica scritta da te è quella giusta. Grazie. :) |
|
|
|
Premoli
Utente giovane
|
Inserito il - 26/06/2011 : 12:25:53
|
Si la spiegazione la trovi sul libro del prof, è un'operazione abbastanza banale, sostanzialmente l'automa rimane lo stesso, ti devi solo ricordare che nell'automa complementato tutti gli stati che prima non erano finali ora diventano finali, mentre gli stati che prima erano finali ora non lo sono più.
Come ti ho già detto prima la funzione di transizione (delta) deve essere totale. ;) |
|
|
|
Evi
Nuovo Utente
|
Inserito il - 28/06/2011 : 11:02:54
|
| Scusa, ma la spiegazione per il complemento nn riesco a trovarla. Mi potresti trovale le pagine corrispondenti del libro? |
|
|
|
Evi
Nuovo Utente
|
Inserito il - 29/06/2011 : 17:00:53
|
| Ho trovato la dimostrazione nella pagina 141 del libro del professore. Mi dispiace ma penso che ti stai sbagliando, visto che questa è una dimostrazione che riguarda la classe dei linguaggi a stati finiti. Per l'esercizio tre, bastava suddividere il linguaggio in altri due(sempre lineari destri) e provare che L era chiuso per il complemento. Infatti il capitolo 5 del libro è pieno di tali esercizi. Cmq, se mi sto sbagliando sentitevi liberi di correggermi. |
|
|
|
Stewie83
Utente medio
Prov.: Brindisi
Città: Brindisi
|
Inserito il - 30/06/2011 : 12:12:20
|
Allora l'esercizio ti chiede una dimostrazione formale....basta che riprendi la dimostrazione facendone riferimento all'esercizio in questione e come detto, dimostri formalmente la chiusura di L3 rispetto al complemento....non è sbagliato fare l'automa che ne riconosce il complemento dato che così dai una dimostrazione vera e propria dato che come ben sapete L3 per kleene coincide con la classe dei linguaggi a stati finiti....L'esercizio in parole povere non ti chiede di dimostrarlo mediante la costruzione dell'automa ma semplicemente facendo un richiamo alla teoria
Spero di essere stato chiaroo |
********a volte è meglio stare in silenzio e passare per deficienti che parlare e dare conferma************************************************ |
|
|
|
roccodigit
Nuovo Utente
Città: Palazzo S.G.
|
Inserito il - 05/07/2011 : 18:09:51
|
punto 3) io con la sola teoria lo sbagliai nel compito. Ma magari l'ho applicata male. Cioè probabilmente bisognava scrivere solo L complementanto = { qui scrivere formalmente tutto X* tranne L}.
Cmq una soluzione completa l'ho trovata dopo facendo gli automi. Se volete cerco di recuperarla e la allego.
punto 2)la grammatica di Premoli è giustissima!
|
Modificato da - roccodigit in data 05/07/2011 18:14:12 |
|
|
| |
Discussione |
|
Appello 10 giugno 2011 (traccia??)
