Sab 24 Agosto, 15:08:11 - 2019

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

0 Utenti e 1 Visitatore stanno visualizzando questo topic.

Offline LOllOStaRR

  • Studente di Dottorato
  • ***
  • Post: 100
  • FeedBack: +13/-6
  • ..what's that?!!
    • Mostra profilo
Esame Linguaggi Modelli e Complessità
« il: Dom 03 Gennaio, 11:14:15 - 2010 »
Poichè io, ma penso anche la gran parte di noi, ho trovato svariate difficoltà nello svolgere gli esercizi di esame proposti, vorrei creare un topic che raccolga soluzioni e ci permetta di confrontarci..in poche parole..
aiutamoseeeeeeeee!
grazie a tutti già da ora..
" dreamed of Paradise
                  every time she closed her eyes.. "

Offline Crabro

  • Direttore di Dipartimento
  • ***
  • Post: 1044
  • FeedBack: +118/-61
    • Mostra profilo
Re: Esame Linguaggi Modelli e Complessità
« Risposta #1 il: Dom 03 Gennaio, 11:33:10 - 2010 »
Sono d'accordissimo. Purtroppo, specialmente per il primo canale, gli esercizi d'esame presentati sono stati ben pochi e non ci farebbe mare vedere lo svolgimento di alcuni.
« Sono convinto che l'informatica abbia molto in comune con la fisica. Entrambe si occupano di come funziona il mondo a un livello abbastanza fondamentale. La differenza, naturalmente, è che mentre in fisica devi capire come è fatto il mondo, in informatica sei tu a crearlo. Dentro i confini del computer, sei tu il creatore. Controlli – almeno potenzialmente – tutto ciò che vi succede. Se sei abbastanza bravo, puoi essere un dio. Su piccola scala. »
   
(Linus Torvalds)

Offline Lorixx89

  • Professore Associato
  • *
  • Post: 641
  • FeedBack: +60/-14
    • Mostra profilo
Re: Esame Linguaggi Modelli e Complessità
« Risposta #2 il: Dom 03 Gennaio, 14:05:54 - 2010 »
Eh si sarebbe una cosa utile, io sinceramente non ci sto capendo quasi una mazza  :-\ Il problema è trovare qualcuno che apra le danze  :asd:

Edit:

1 - Si potrebbe iniziare illustrando dei procedimenti pratici per passare da un linguaggio ad automa a pila, anche nel caso di macchine di turing (non capisco il meccanismo)!

2 - Spiegare in modo molto più umano il funzionamento e l'applicazione ad esempi pratici del pumping lemma  :asd:

3 - Scommetto che non sono l'unico che scapoccia sulla riduzione in forma di greibach  :sisi:

4 - Definire una macchina di turing deterministica con alfabeto di input {0,1} che accetta tutte le stringhe di lunghezza dispari e rifiuta tutte le altre.


Questo sarebbe gia un ottimo inizio  ;)
« Ultima modifica: Dom 03 Gennaio, 15:17:23 - 2010 da Lorixx89 »

Offline JackDuluoz

  • Studente di Dottorato
  • ***
  • Post: 171
  • FeedBack: +18/-4
    • Mostra profilo
    • Mind Unpacked
Re: Esame Linguaggi Modelli e Complessità
« Risposta #3 il: Mar 05 Gennaio, 11:52:45 - 2010 »
Anch'io sono mooolto in difficolta' con la parte di modelli, ora sto provando a fare qualche cosa e se riesco magari posto, ma sarebbe bello se qualcuno piu' bravo potrebbe darci una mano (tipo con i punti indicati da Lorixx) :asd:

Offline JackDuluoz

  • Studente di Dottorato
  • ***
  • Post: 171
  • FeedBack: +18/-4
    • Mostra profilo
    • Mind Unpacked
Re: Esame Linguaggi Modelli e Complessità
« Risposta #4 il: Mar 05 Gennaio, 12:41:04 - 2010 »
Vabbe' comincio io a scrivere qualcosa, mi riferisco a questo testo d'esame: http://www.dis.uniroma1.it/~fiii/esame/4.appello--15-07-2009/Esame%2015%20luglio.pdf in particolare solamente alla prima domanda, per ora :asd:

Il punto 1a) e' abbastanza facile, anche la dimostrazione si trova sul libro ed e' piuttosto comprensibile (rispetto a molte altre)
Per quanto riguarda il punto 1b) ho trovato la seguente grammatica:
Codice: [Seleziona]
S -> aBc
B -> aBc | R
R -> bR | b

che mi sembra sia corretta. Sulla dimostrazione non sono sicuro, ma siccome tutti i linguaggi regolari devono avere una struttra delle produzioni come la seguente:
Codice: [Seleziona]
A -> d, A € V(n), d € (V(n) ° V(t)) U V(t)e le produzione di questa grammatica non ce l'hanno, allora il linguaggio non e' regolare.
Qualcuno smentisce o conferma cio'?  ;D

Offline Lorixx89

  • Professore Associato
  • *
  • Post: 641
  • FeedBack: +60/-14
    • Mostra profilo
Re: Esame Linguaggi Modelli e Complessità
« Risposta #5 il: Mar 05 Gennaio, 13:08:16 - 2010 »
Ma per dimostrare che una grammatica non è regolare non si usa appunto il pumping lemma per i linguaggi regolari..???

Edit : Confermato, quello si dimostra con il pumping lemma, o il teorema di Myhill-Nerode!
« Ultima modifica: Mar 05 Gennaio, 13:14:19 - 2010 da Lorixx89 »

Offline JackDuluoz

  • Studente di Dottorato
  • ***
  • Post: 171
  • FeedBack: +18/-4
    • Mostra profilo
    • Mind Unpacked
Re: Esame Linguaggi Modelli e Complessità
« Risposta #6 il: Mar 05 Gennaio, 13:53:40 - 2010 »
Gia', hai ragione... sono rovinato :asd:

Offline Ghost

  • Ricercatore
  • ****
  • Post: 308
  • FeedBack: +28/-13
    • Mostra profilo
Re: Esame Linguaggi Modelli e Complessità
« Risposta #7 il: Mar 05 Gennaio, 15:13:35 - 2010 »
sì, per definizione si utilizza il pumping lemma, ma mi pare di aver capito che non è l'unico modo per dimostrare che un linguaggio non è regolare... sicuramente è uno dei più semplici (secondo altri) :asd:
« Ultima modifica: Mar 05 Gennaio, 15:16:23 - 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 #8 il: Mar 05 Gennaio, 16:55:42 - 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

Offline Ghost

  • Ricercatore
  • ****
  • Post: 308
  • FeedBack: +28/-13
    • Mostra profilo
Re: Esame Linguaggi Modelli e Complessità
« Risposta #9 il: Mar 05 Gennaio, 16:56:39 - 2010 »
l'unica dimostrazione che mi viene in mente, applicando il pumping lemma, è questa:
supponiamo a(^n)b(^m)c(^n)=uvw=z.
allora se v contiene due simboli diversi (ad es. v=ab), allora la stringa uv(^2)w contiene un'alternanza di simboli incompatibili con a(^n)b(^m)c(^n), cioè, ad esempio, la stringa aababc non appartiene al linguaggio!
non sono sicuro sulla validità della dimostrazione  ???
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 Ghost

  • Ricercatore
  • ****
  • Post: 308
  • FeedBack: +28/-13
    • Mostra profilo
Re: Esame Linguaggi Modelli e Complessità
« Risposta #10 il: Mar 05 Gennaio, 17:07:38 - 2010 »
sì, direi che è molto più valida la dimostrazione di JackDuluoz  :asd:
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 redeire

  • Studente di Dottorato
  • ***
  • Post: 248
  • FeedBack: +32/-34
    • Mostra profilo
Re: Esame Linguaggi Modelli e Complessità
« Risposta #11 il: Mar 05 Gennaio, 17:38:52 - 2010 »
Esercizio 4  ::)

q0->se trova 0 o 1 va in q1 e la testina si sposta a destra
q1->se trova 0 o 1 va in q0 e la testina si sposta a destra, se trova "blank" va in qF
qf ->stato finale.
"'Scuse me while I kiss the sky"
                  ^

Exception in thread "main"
    java.lang.ArrayIndexOutOfBoundsException......

Offline Ghost

  • Ricercatore
  • ****
  • Post: 308
  • FeedBack: +28/-13
    • Mostra profilo
Re: Esame Linguaggi Modelli e Complessità
« Risposta #12 il: Mar 05 Gennaio, 18:03:53 - 2010 »
Ragazzi, qualcuno sà rispondere a questo quesito?
Citazione
3b) Sia data una Macchina di Turing con 3 stati. Siano date le variabili proposizionali q1,
q2, q3 che rappresentano il fatto che la macchina si trova in uno dei tre stati. Esprimere
con una formula della logica proposizionale in forma normale congiuntiva il fatto che la
macchina deve essere in uno dei tre stati ma non può essere contemporaneamente in due
diversi stati. Indicare quali sono i modelli della formula.
Non sembra difficile, ma non sò da dove iniziare  ???
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 #13 il: Mar 05 Gennaio, 18:39:30 - 2010 »
Ho trovato questa formula (al posto di q1, q2 e q2 scrivo a, b, c; il segno - indica il not):
Codice: [Seleziona]
(a v b v c) ^ (-a v -b) ^ (-a v -c) ^ (-b v -c)La prima clausola serve perche' la macchina deve trovarsi necessariemente in uno dei tre stati, se tutti sono false allora la formula e' false; gli altri servono a garantire che non si possa trovare in tre stati contemporaneamente, infatti quando, per esempio a e b sono entrambi true la seconda clausola diventa false, la stessa cosa vale per le altre.
Per quanto riguarda i modelli... non ne ho la minima idea, non avendo seguito sto cercando di capire dalle slide... ma bho

Offline Tom89

  • Professore Ordinario
  • **
  • Post: 703
  • FeedBack: +145/-79
    • Mostra profilo
Re: Esame Linguaggi Modelli e Complessità
« Risposta #14 il: Mar 05 Gennaio, 18:57:33 - 2010 »
I modelli sono semplicemente tutte le proposizioni che rendono valida la formula che hai scritto...
per fortuna in questo caso abbiamo la definizione "intuitiva" del modello, e quindi possiamo limitarci a scrivere le 3 proposizioni dove è vero un solo letterale:

(A), (B), (C)

credo  :asd: