<div dir="ltr"><div class="gmail_extra"><div class="gmail_quote">2015-06-25 20:22 GMT+01:00 Carlos Catucci <span dir="ltr"><<a href="mailto:carlos.catucci@gmail.com" target="_blank">carlos.catucci@gmail.com</a>></span>:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr"><span class=""><div class="gmail_extra"><div class="gmail_quote"><br></div></div></span><div class="gmail_extra">QUando Enrico parla a braccio io incido nella pietra quel che dice. Cosi', per stare sul sicuro ;)<span class="HOEnZb"><font color="#888888"><br></font></span></div><span class="HOEnZb"><font color="#888888"><div class="gmail_extra"><br></div></font></span></div></blockquote><div><br></div><div>Grazie della fiducia, ma qui il disclaimer e' importante. Intanto la "teoria" di cui si parla e' roba che studiai davvero tipo 12 anni fa (quindi ci sono innumerevoli problemi di cache miss). Dopo di che in teoria il discorso e' "il linguaggio X ha determinate proprieta' formali"... </div><div><br></div><div>In particolare, dimostrare che un linguaggio e' context free (o regolare) ci sono alcuni approcci. Un primo approccio (che a volte funziona) e' quello di scriverlo in un formalismo che mostra che e' context free (o regolare). Per esempio si puo' esibire un  automa a pila (o un DFA) che lo accetta. Oppure si scrive una grammatica context-free (o un'espressione regolare) che lo accetta.</div><div><br></div><div>La cosa divertente e' che questo e' molto complicato: siccome tipicamente un linguaggio e' specificato in un qualche formalismo da chi ha fatto lo standard e tu hai il tuo formalismo per accettarlo, dimostrare formalmente che il linguaggio descritto dai due orpelli e' lo stesso non e' in generale facile. Specie quando parliamo di linguaggi general purpose, che sono oggetti parecchio complicati.</div><div><br></div><div>Da cui per esempio tutto il discorso su Java: hai una specifica che *sembra* CFG, ma lascia aperte delle porte (ovvero il formalismo ha qualche ambiguita' che viene risolta con una convenzione: e bisogna capire se quella convenzione per caso non lo fa uscire dalla CFG). Pero' capisci che parlare di "mi sembra" e "ritengo" quando si parla di matematica "dura" e' abbastanza poco professionale.</div><div><br></div><div>Ah, dimenticavo: il fatto di mettersi ad esibire grammatiche e automi che riconoscono un certo linguaggio (e dimostrare che riconoscono *esattamente* quel linguaggio) non e' in generale banale. Manco per linguaggi semplici. E allora di solito si usa il pumping lemma (o altre cose del genere). Che sebbene sia formulato in positivo, generalmente si usa in negativo (ovvero per dimostrare che un linguaggio non e' CF -- regolare -- mostrando una determinata famiglia di stringhe -- programmi -- nel linguaggio che violano il suddetto lemma). Che e' sufficientemente complicato quando il tuo linguaggio parla di un stringa di n 0 seguita da n 1, figurati per un linguaggio di programmazione vero e proprio.</div></div><br clear="all"><div><br></div>-- <br><div class="gmail_signature"> .<br>..: -enrico-</div>
</div></div>