| V I S U A L I Z Z A D I S C U S S I O N E |
| roccodigit |
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!! |
| 11 U L T I M E R I S P O S T E (in alto le più recenti) |
| roccodigit |
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!
|
| Stewie83 |
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 |
| Evi |
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. |
| Evi |
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? |
| Premoli |
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. ;) |
| Piplos |
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. :) |
| Piplos |
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? |
| Premoli |
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 |
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? |
| roccodigit |
Inserito il - 19/06/2011 : 20:22:16
Si grazie, dovrebbe essere cosi ;) |
| Marsigliese |
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}.
|
