Dom 18 Agosto, 06:36:05 - 2019

Autore Topic: Esame Linguaggi Modelli e Complessità  (Letto 8878 volte)

0 Utenti e 1 Visitatore stanno visualizzando questo topic.

Offline Ghost

  • Ricercatore
  • ****
  • Post: 308
  • FeedBack: +28/-13
    • Mostra profilo
Re: Esame Linguaggi Modelli e Complessità
« Risposta #15 il: Mar 05 Gennaio, 19:08:40 - 2010 »
sì, sembra essere proprio così  :asd:
allora vi ringrazio e pongo un altro quesito:
Citazione
3a) Dimostrare che l’insieme di connettivi {nand} costituisce un insieme completo per il
calcolo proposizionale.
stò cercando di capire dalle slide, ma non arrivo ancora ad una soluzione plausibile  ???
« Ultima modifica: Mar 05 Gennaio, 19:10:19 - 2010 da Ghost »
Homo Faber Fortunae Suae.

Un progettista capisce di aver raggiunto la perfezione non quando
non c'è più niente da aggiungere, ma quando non c'è più niente da togliere.  [Antoine de Saint-Exupéry, "Terres des hommes"]

Offline JackDuluoz

  • Studente di Dottorato
  • ***
  • Post: 171
  • FeedBack: +18/-4
    • Mostra profilo
    • Mind Unpacked
Re: Esame Linguaggi Modelli e Complessità
« Risposta #16 il: Mer 06 Gennaio, 16:37:44 - 2010 »
Chi sa dimostrare questo? Io ho in mente qualcosa ma non so se puo' andare.
Citazione
1b) Mostrare che la classe dei linguaggi regolari è chiusa rispetto alla inversione delle
stringhe (cioè se il linguaggio L è regolare anche il linguaggio LR che contiene tutte e
sole le stringhe di L invertite è regolare).

Offline Ntonigà

  • Professore Associato
  • *
  • Post: 542
  • FeedBack: +56/-13
    • Mostra profilo
Re: Esame Linguaggi Modelli e Complessità
« Risposta #17 il: Mer 06 Gennaio, 17:19:18 - 2010 »
sì, sembra essere proprio così  :asd:
allora vi ringrazio e pongo un altro quesito:stò cercando di capire dalle slide, ma non arrivo ancora ad una soluzione plausibile  ???

Sul quaderno ho qualcosa... Ma ricordo a lezione di non aver colto a pieno la questione di 2^2^n.
Ho gli appunto troppo vaghi su questo punto...Chi ha seguito con Ausiello dovrebbe avere qualcosa era la lezione del 30/9/9
"Il software è come il sesso, è migliore quando è libero."

Offline Tom89

  • Professore Ordinario
  • **
  • Post: 703
  • FeedBack: +145/-79
    • Mostra profilo
Re: Esame Linguaggi Modelli e Complessità
« Risposta #18 il: Mer 06 Gennaio, 17:44:21 - 2010 »
sì, sembra essere proprio così  :asd:

Citazione
3a) Dimostrare che l’insieme di connettivi {nand} costituisce un insieme completo per il
calcolo proposizionale.

allora vi ringrazio e pongo un altro quesito:stò cercando di capire dalle slide, ma non arrivo ancora ad una soluzione plausibile  ???

Allora;
credo sia sufficiente dimostrare l'equivalenza di nand ad un'altro insieme completo; facciamo (and, not).

dato che a nand b = not( a and b ) possiamo riscrivere

not a = a nand a
a and b = not ( a nand b ) = (a nand b) nand (a nand b)

e dato che è possibile riscrivere le operazioni di un insieme completo in termini di nand, nand è un insieme completo.

Tutto qua, anche se temo sia troppo discorsivo per l'esame  :sisi:

PS: ma che vuol dire orario esame 9 - 19  :o
« Ultima modifica: Mer 06 Gennaio, 18:01:21 - 2010 da Tom89 »

Offline Ntonigà

  • Professore Associato
  • *
  • Post: 542
  • FeedBack: +56/-13
    • Mostra profilo
Re: Esame Linguaggi Modelli e Complessità
« Risposta #19 il: Mer 06 Gennaio, 17:52:36 - 2010 »
allora vi ringrazio e pongo un altro quesito:stò cercando di capire dalle slide, ma non arrivo ancora ad una soluzione plausibile  ???


Allora;
credo sia sufficiente dimostrare l'equivalenza di nand ad un'altro insieme completo; facciamo (and, not).

dato che a nand b = not( a and b ) possiamo riscrivere

not a = a nand a
a and b = not ( a nand b ) = (a nand b) nand (a nand b)

Tutto qua  :sisi:

Ecco che gli appunti prendono senso!  :sisi:
Grazie Tom ottimo!  ;)
"Il software è come il sesso, è migliore quando è libero."

Offline Lorixx89

  • Professore Associato
  • *
  • Post: 641
  • FeedBack: +60/-14
    • Mostra profilo
Re: Esame Linguaggi Modelli e Complessità
« Risposta #20 il: Gio 07 Gennaio, 14:19:32 - 2010 »
Ok... l'ho dimostrato col pumping lemma, qualcuno mi dice se e' giusto?

Le stringhe del linguaggio sono della forma apbqcp. Se il linguaggio fosse regolare ogni stringa di lunghezza maggiore uguale ad un opportuno n potrebbe essere scritta come concatenazione di tre stringe uvw tali che |uv| <= n, |v| >= 1 e uviw € L per ogni i >= 1.
Se scegliamo p > n abbiamo che, poiche' dobbiamo soddisfare la condizione |uv| <= n, dobbiamo scegliere u = ε, v = an, w = ap-nbqcp. Per il pumping lemma tutte le stringhe della forma uviw e quindi aniap-nbqcp dovrebbero appartenere a L per ogni i; la cosa non si verifica e quindi L non e' regolare.

Vi prego datemi una conferma ;D

Me lo puoi spiegare in modo un po + intuitivo?  :'( Grazie

Offline love636

  • Direttore di Dipartimento
  • ***
  • Post: 2451
  • FeedBack: +93/-40
    • Mostra profilo
Re: Esame Linguaggi Modelli e Complessità
« Risposta #21 il: Gio 07 Gennaio, 17:17:11 - 2010 »
Codice: [Seleziona]
Domanda 1
1a) Fornire una traccia della dimostrazione che ogni linguaggio di tipo 2 è riconoscibile
con un automa a pila non deterministico.
1b) Si consideri la seguente grammatica:
S --> aSHa | bSHb | a | b
H --> ε | Z
Z --> zZ
Dire che linguaggio genera e costruire l’automa a pila che riconosce il linguaggio stesso.

Chi riesce a farlo??

mi sembra che il linguaggio che genera è quello delle strinnghe palindrome.....dico bene?
I love my 636 "E' un paese L'italia ...."
                                                               Marco Masini

Offline JackDuluoz

  • Studente di Dottorato
  • ***
  • Post: 171
  • FeedBack: +18/-4
    • Mostra profilo
    • Mind Unpacked
Re: Esame Linguaggi Modelli e Complessità
« Risposta #22 il: Gio 07 Gennaio, 17:20:37 - 2010 »
Si, allora:
Se il linguaggio fosse regolare ogni stringa di lunghezza maggiore uguale ad un opportuno n potrebbe essere scritta come concatenazione di tre stringe uvw tali che |uv| <= n, |v| >= 1 e uviw € L per ogni i >= 1.
Questa e' la definizione data dal pumping lemma.

Citazione
Se scegliamo p > n
Lo scegliamo maggiore cosi' la lunghezza della stringa sara' sicuramente > n e, per definizione, dovra' soddisfare il pumping lemma.

Citazione
abbiamo che, poiche' dobbiamo soddisfare la condizione |uv| <= n, dobbiamo scegliere u = ε, v = an, w = ap-nbqcp.
In pratica, dobbiamo riscrivere la string a apbqcp come concatenazione di u, v e w rispettando quei vincoli. La lunghezza di uv cioe' la prima parte deve essere
<= n, quindi la stringa uv sara' composta solamente da 'a'... visto che il carattere a viene ripetuto per p volte e p e' piu' lungo di n. Di conseguenza scegliamo u come stringa vuota, e  v = an. Potremmo anche scegliere u = a e v = n-1, non cambia niente, e' solo per semplicita', tanto sulla stringa u non si hanno vincoli da rispettare. La restante stringa sara' w che quindi comprendera' sia i caratteri 'a' che non sono inclusi dalla stringa v e che saranno in numero p-n, sia la parte rimanente bqcp.


Citazione
Per il pumping lemma tutte le stringhe della forma uviw e quindi aniap-nbqcp dovrebbero appartenere a L per ogni i; la cosa non si verifica e quindi L non e' regolare.

Basta sostituire al posto di uvw le stringhe che gli abbiamo assegnato e verificare che il risultato non appartiene a L al variare di i; basta scegliere i != 1 per generare una stringa che non appartiene a L, quindi il linguaggio non e' regolare.

Offline Lorixx89

  • Professore Associato
  • *
  • Post: 641
  • FeedBack: +60/-14
    • Mostra profilo
Re: Esame Linguaggi Modelli e Complessità
« Risposta #23 il: Ven 08 Gennaio, 10:29:10 - 2010 »
Ho capito, ti ringrazio tantissimo!

Offline andrea89

  • Author
  • Professore Ordinario
  • **
  • Post: 733
  • FeedBack: +76/-17
    • Mostra profilo
Re: Esame Linguaggi Modelli e Complessità
« Risposta #24 il: Ven 08 Gennaio, 18:03:39 - 2010 »
allora vi ringrazio e pongo un altro quesito:stò cercando di capire dalle slide, ma non arrivo ancora ad una soluzione plausibile  ???


Allora;
credo sia sufficiente dimostrare l'equivalenza di nand ad un'altro insieme completo; facciamo (and, not).

dato che a nand b = not( a and b ) possiamo riscrivere

not a = a nand a
a and b = not ( a nand b ) = (a nand b) nand (a nand b)

e dato che è possibile riscrivere le operazioni di un insieme completo in termini di nand, nand è un insieme completo.

Tutto qua, anche se temo sia troppo discorsivo per l'esame  :sisi:

PS: ma che vuol dire orario esame 9 - 19  :o

ho trovato questo:
l connettivo NAND è funzionalmente completo, cioè da questo solo connettivo è possibile derivare gli altri.

NAND(A,A) = \negA

NAND(NAND(A,B),NAND(A,B)) = A ∧ B

NAND(NAND(A,A),NAND(B,B)) = A ∨ B

NAND(NAND(A,B),A) = A → B
ll computer non è una macchina intelligente che aiuta le persone
stupide, anzi è una macchina stupida che funziona solo nelle mani delle persone intelligenti (Umberto Eco).

Offline Tom89

  • Professore Ordinario
  • **
  • Post: 703
  • FeedBack: +145/-79
    • Mostra profilo
Re: Esame Linguaggi Modelli e Complessità
« Risposta #25 il: Dom 10 Gennaio, 17:15:16 - 2010 »
Chi sa dimostrare questo? Io ho in mente qualcosa ma non so se puo' andare.
Citazione
1b) Mostrare che la classe dei linguaggi regolari è chiusa rispetto alla inversione delle
stringhe (cioè se il linguaggio L è regolare anche il linguaggio LR che contiene tutte e
sole le stringhe di L invertite è regolare).

Si potrebbe fare così?

Dato che per definizione dei linguaggi regolari L è definito da una Espressione Regolare, LR è definito da una espressione regolare invertita, poichè ricorsivamente è possibile invertire le operazioni non commutative come °: L(A) ° L(B) = L(B) ° L(A).
Per cui LR rimane di tipo 3 potendo esprimerlo tramite una ER.

Fa acqua da tutte le parti ma altre dimostrazioni non mi vengono...

Offline Ntonigà

  • Professore Associato
  • *
  • Post: 542
  • FeedBack: +56/-13
    • Mostra profilo
Re: Esame Linguaggi Modelli e Complessità
« Risposta #26 il: Dom 10 Gennaio, 17:27:49 - 2010 »


Si potrebbe fare così?

Dato che per definizione dei linguaggi regolari L è definito da una Espressione Regolare, LR è definito da una espressione regolare invertita, poichè ricorsivamente è possibile invertire le operazioni non commutative come °: L(A) ° L(B) = L(B) ° L(A).
Per cui LR rimane di tipo 3 potendo esprimerlo tramite una ER.

Fa acqua da tutte le parti ma altre dimostrazioni non mi vengono...


Si potrebbe sfruttare il fatto che i linguaggi regolari sono riconosciuti da automi a stati finiti e dunque per una qualunque stringa appartenente ad un linguaggio regolare so costruire l'automa deterministico che ne riconosce l'inversa creando un nuovo automa che sia il trasposto di quello iniziale con stato finale e stato iniziale invertiti e dunque ho creato un automa che riconosce un linguaggio regolare. CVD  ;D
"Il software è come il sesso, è migliore quando è libero."

Offline Tom89

  • Professore Ordinario
  • **
  • Post: 703
  • FeedBack: +145/-79
    • Mostra profilo
Re: Esame Linguaggi Modelli e Complessità
« Risposta #27 il: Dom 10 Gennaio, 17:43:40 - 2010 »
Si potrebbe sfruttare il fatto che i linguaggi regolari sono riconosciuti da automi a stati finiti e dunque per una qualunque stringa appartenente ad un linguaggio regolare so costruire l'automa deterministico che ne riconosce l'inversa creando un nuovo automa che sia il trasposto di quello iniziale con stato finale e stato iniziale invertiti e dunque ho creato un automa che riconosce un linguaggio regolare. CVD  ;D


E' vero potrebbe funzionare... l'unico dubbio rimane sulle stringhe vuote: se lo stato iniziale è finale sia per riconoscere la stringa vuota sia per altro, non si ha un problema per l'inversione?

Offline Ntonigà

  • Professore Associato
  • *
  • Post: 542
  • FeedBack: +56/-13
    • Mostra profilo
Re: Esame Linguaggi Modelli e Complessità
« Risposta #28 il: Dom 10 Gennaio, 17:53:35 - 2010 »
E' vero potrebbe funzionare... l'unico dubbio rimane sulle stringhe vuote: se lo stato iniziale è finale sia per riconoscere la stringa vuota sia per altro, non si ha un problema per l'inversione?


No perchè se ci pensi un attimo l'automa che riconosce le stringhe vuote ha un solo stato che è iniziale e finale.
Se costruisci il trasposto scambiando stato iniziale con finale ti accorgerai tu stesso che ottieni sempre lo stesso stato iniziale e finale.  ;)
"Il software è come il sesso, è migliore quando è libero."

Offline Tom89

  • Professore Ordinario
  • **
  • Post: 703
  • FeedBack: +145/-79
    • Mostra profilo
Re: Esame Linguaggi Modelli e Complessità
« Risposta #29 il: Dom 10 Gennaio, 19:17:16 - 2010 »
No aspe eccolo il problema.
Se gli stati finali sono più d'uno che si fa? E' impossibile :sisi: