Mer 21 Agosto, 09:32:54 - 2019

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

0 Utenti e 1 Visitatore stanno visualizzando questo topic.

Offline lucaskywalker

  • Studente di Dottorato
  • ***
  • Post: 176
  • FeedBack: +35/-2
    • Mostra profilo
Re: Esame Linguaggi Modelli e Complessità
« Risposta #60 il: Sab 06 Febbraio, 16:43:49 - 2010 »
il prof a lezione riusava le stesse lettere!!!altrimenti poi ti vengono troppe variabili..

Offline lucaskywalker

  • Studente di Dottorato
  • ***
  • Post: 176
  • FeedBack: +35/-2
    • Mostra profilo
Re: Esame Linguaggi Modelli e Complessità
« Risposta #61 il: Lun 08 Febbraio, 11:09:39 - 2010 »
Compito 15 luglio 2009

2b) Definire il problema decisionale VERTEX COVER (ricoprimento degli archi di un
grafo mediante nodi). Mostrare una istanza positiva e una negativa con almeno 5 nodi e 8
archi. Dimostrare che VERTEX COVER appartiene ad NP.


come faccio a mostrare un istanza positiva ed una negativa con 5 nodi e 8 archi????

Offline genietta

  • Studente di Dottorato
  • ***
  • Post: 174
  • FeedBack: +35/-15
    • Mostra profilo
Re: Esame Linguaggi Modelli e Complessità
« Risposta #62 il: Gio 24 Giugno, 22:11:51 - 2010 »
Compito 15 luglio 2009

2b) Definire il problema decisionale VERTEX COVER (ricoprimento degli archi di un
grafo mediante nodi). Mostrare una istanza positiva e una negativa con almeno 5 nodi e 8
archi. Dimostrare che VERTEX COVER appartiene ad NP.


come faccio a mostrare un istanza positiva ed una negativa con 5 nodi e 8 archi????

C'è qualcuno che lo ha risolto?  :-[

Offline Pir@t

  • Neo-Laureato
  • **
  • Post: 56
  • FeedBack: +4/-2
    • Mostra profilo
Re: Esame Linguaggi Modelli e Complessità
« Risposta #63 il: Ven 13 Gennaio, 15:42:51 - 2012 »
Dal esame 7/2/2011
1a) mostare un esempio di grammatica tipo 3 che genera un linguaggio infinito e per tale esempio mostrare 3 stringhe che appartengono al linguaggio generato e 3 stringhe che non appartengono.

Come soluzione: S->aS
s1=aS; s2=aSS; s3=aSS che appartengono e
c1=a; c2=aa; c3=aaa che non appartengono al linguaggio

Va bene cosi?

Offline Pir@t

  • Neo-Laureato
  • **
  • Post: 56
  • FeedBack: +4/-2
    • Mostra profilo
Re: Esame Linguaggi Modelli e Complessità
« Risposta #64 il: Ven 13 Gennaio, 16:39:04 - 2012 »
1b) Dato L={ww^r | w{a,b}^+} fornire L*

Quindi: S->aA|bB
            A->Sa|a
            B->Sb|b

Offline Jaikappa

  • Ricercatore
  • ****
  • Post: 389
  • FeedBack: +54/-1
    • Mostra profilo
    • Il mio paese
Re: Esame Linguaggi Modelli e Complessità
« Risposta #65 il: Ven 13 Gennaio, 18:16:35 - 2012 »
Dal esame 7/2/2011
1a) mostare un esempio di grammatica tipo 3 che genera un linguaggio infinito e per tale esempio mostrare 3 stringhe che appartengono al linguaggio generato e 3 stringhe che non appartengono.

Come soluzione: S->aS
s1=aS; s2=aSS; s3=aSS che appartengono e
c1=a; c2=aa; c3=aaa che non appartengono al linguaggio

Va bene cosi?
Guarda sinceramente non ti so dire con certezza se sia corretta o meno la tua soluzione.

A tal proposito andai a ricevimento e il prof mi propose come soluzione:
A--> aA | a come grammatica
Linguaggi che appartengono: a , aa , aaa
Linguaggi che non appartengono: banalmente b , ecc..

Offline Robert

  • Professore Ordinario
  • **
  • Post: 837
  • FeedBack: +87/-28
    • Mostra profilo
Re: Esame Linguaggi Modelli e Complessità
« Risposta #66 il: Ven 13 Gennaio, 18:21:02 - 2012 »
Dal esame 7/2/2011
1a) mostare un esempio di grammatica tipo 3 che genera un linguaggio infinito e per tale esempio mostrare 3 stringhe che appartengono al linguaggio generato e 3 stringhe che non appartengono.

Come soluzione: S->aS
s1=aS; s2=aSS; s3=aSS che appartengono e
c1=a; c2=aa; c3=aaa che non appartengono al linguaggio

Va bene cosi?


Non credo vada bene la grammatica S->aS, perché non genera mai una stringa di soli terminali, quindi in pratica quel linguaggio è vuoto, quindi finito.

Linguaggio infinito significa che può generare un numero infinito di stringhe.

Un esempio potrebbe essere questa:
S->aS, b

che è relativa al linguaggio L={anb | n>=0}


Il linguaggio che ho scritto io genera tutte le stringhe che terminano con il carattere b e che hanno un numero arbitrario di a che lo precedono.

Appartengono stringhe del tipo: b, ab, aab, aaab ecc...
Non appartengono: a, ba, aba, bbaba ecc...


1b) Dato L={ww^r | w{a,b}^+} fornire L*

Quindi: S->aA|bB
            A->Sa|a
            B->Sb|b

Qui si chiede L* su un L che genera stringhe palindrome di a e b.
Deve poter generare anche la stringa vuota (dato che è presente *), quindi potrebbe essere più o meno così (e=epsilon):


S' -> S | e
S -> T
T -> aTa | bTb | aa | bb

Offline Pir@t

  • Neo-Laureato
  • **
  • Post: 56
  • FeedBack: +4/-2
    • Mostra profilo
Re: Esame Linguaggi Modelli e Complessità
« Risposta #67 il: Ven 13 Gennaio, 18:40:33 - 2012 »
Citazione
Non credo vada bene la grammatica S->aS, perché non genera mai una stringa di soli terminali, quindi in pratica quel linguaggio è vuoto, quindi finito.

Linguaggio infinito significa che può generare un numero infinito di stringhe.

Un esempio potrebbe essere questa:
S->aS, b

D'accordo!Grazie!)

Però, non avevo capito  bene la domanda con L*, perchè L*={(wwr)* | w={a,b}+}. In teoria non deve essere vuoto perchè {a,b} con + e non con *. Cmq. se dovessi generare stringa vuota, allora si aggiunge S'->S|e come fatto tu e stiamo a posto;)

Offline Robert

  • Professore Ordinario
  • **
  • Post: 837
  • FeedBack: +87/-28
    • Mostra profilo
Re: Esame Linguaggi Modelli e Complessità
« Risposta #68 il: Ven 13 Gennaio, 18:52:41 - 2012 »
D'accordo!Grazie!)

Però, non avevo capito  bene la domanda con L*, perchè L*={(wwr)* | w={a,b}+}. In teoria non deve essere vuoto perchè {a,b} con + e non con *. Cmq. se dovessi generare stringa vuota, allora si aggiunge S'->S|e come fatto tu e stiamo a posto;)

Il + è riferito ai simboli del linguaggio L, nel senso che non ammette stringhe vuote. L'asterisco del linguaggio da trovare indica che esso conterrà anche la stringa vuota.

Però mi sono accorto di aver sbagliato. Quello che ho scritto io genera stringhe palindrome + stringa vuota.

Invece L* deve generare cose del tipo: aabbaaabbbabba, ovvero stringhe composte da palindrome.

Quindi c'è da rivederlo, ora provo a farlo.

edit

Per ora mi viene così:

S' ⟶ ε | S
S ⟶ A | B | AS | BS
A ⟶ aAa | aBa | aa
B ⟶ bBb | bAb | bb

Una stringa di prova potrebbe essere: aa-bb-abaaba (ho separato le palindrome concatenate ma è un'unica stringa ovviamente).

La posso ottenere con le produzioni:
S' ⟶ S                   S
S ⟶ AS                 AS
A ⟶ aa                 aaS
S ⟶ BS                aaBS
B ⟶ bb                aabbS
S ⟶ A                 aabbA
A ⟶ aBa             aabbaBa
B ⟶ bAb            aabbabAba
A ⟶ aa             aabbabaaba

A occhio e croce mi pare corretta, ma non si sa mai.
« Ultima modifica: Ven 13 Gennaio, 19:19:28 - 2012 da Robert »

Offline Pir@t

  • Neo-Laureato
  • **
  • Post: 56
  • FeedBack: +4/-2
    • Mostra profilo
Re: Esame Linguaggi Modelli e Complessità
« Risposta #69 il: Sab 14 Gennaio, 15:46:14 - 2012 »
Ho pensato, che si può fare anche come:
S->T|e
T->Z|ZT
Z->aZa|bZb|aa|bb

Cosi, possiamo generare N volte wwr con ZT, ad esempio 3 volte:
S->T->ZT->ZZT->ZZZ ecc. e poi ogni Z genera la sua stringa palindroma wwr

Sembra che funziona...

Offline Robert

  • Professore Ordinario
  • **
  • Post: 837
  • FeedBack: +87/-28
    • Mostra profilo
Re: Esame Linguaggi Modelli e Complessità
« Risposta #70 il: Sab 14 Gennaio, 16:11:01 - 2012 »
Mi sembra di sì.

Offline Adelscott

  • Professore Associato
  • *
  • Post: 662
  • FeedBack: +34/-5
    • Mostra profilo
Re:Esame Linguaggi Modelli e Complessità
« Risposta #71 il: Gio 01 Novembre, 19:58:07 - 2012 »
Ragazzi qualcuno potrebbe aiutarmi con queste domande:

2a) Definire le classi P, NP, PSPACE, EXPTIME. Che relazioni sono note tra le suddette
classi? Se sappiamo che un problema è risolubile in spazio n2 con una MT deterministica
a k nastri, quanto tempo può richiedere la sua soluzione?
2b) Definire il problema della programmazione lineare con variabili 0 o 1. Mostrare una
istanza positiva e una istanza negativa. Se si dimostrasse che la soluzione di tale
problema richiede necessariamente tempo 2n che conseguenze si potrebbero trarre sulla
questione della relazione tra P ed NP?

I miei problemi sono sulla seconda parte della 2a e sulla prima parte di 2b(istanza positiva e negativa)..... Grazieeee
Io rappresento per l'infame quello che per un computer rappresenta un virus. [Art. 31]