Questa è la traccia: Sia data la seguente grammatica lineare destra G = (X, V, S, P) ove X = {a, b}, V = {S, A, B}, P = { S --> aS | aA | aB | a, A --> bS } Determinare una espressione regolare che denota L(G).
S = aS+abS+a --> S= (a+ab)*S +a Questa espressione è nella forma R1= R2*R1+R3 e per le proprietà sulle espressioni regolari diventa R1= R2star * R3 quindi--> S= (a+ab)star *a ed una espressione regolare che denota L(G) è proprio questa. Credo sia così ma non sono sicuro al cento per cento
La produzione S->aB viene eliminata dalla grammatca in quanto inutile.
Se dovessimo eliminare tutto ciò che inutile, il mondo sarebbe tremendamente vuoto (che sto dicendo?)
E' un bene per il Prof. Xxxxxxx che sappia con chi ha a che fare. Pensa a studiare e non agli esempi, o ad altre strade per così dire, che questa volta mi sa che non attacca. [cit.]
Tutti professori dall'esterno, e poi parlano persone che per prendere un voto decente ripetono l'esame 30 volte e poi fanno i sapientoni con chi segue la prima volta vedi chilavert [cit.]
prof volevo porle una domanda, ci sono degli esercizi tipo: dimostrare formalmente che il seguente linguaggio L ={ a^i b^j c^k : K=min{i,j}, i,j>=0} non è lineare destro.
come si svolge a grandi linee? ed inoltre può essere traccia d'esame?
grazie.
L'UOMO COMUNE RAGIONA,IL SAGGIO TACE,IL FESSO DISCUTE.
prof volevo porle una domanda, ci sono degli esercizi tipo: dimostrare formalmente che il seguente linguaggio L ={ a^i b^j c^k : K=min{i,j}, i,j>=0} non è lineare destro.
come si svolge a grandi linee? ed inoltre può essere traccia d'esame?
grazie.
Si svolge usando il pumping lemma per i linguaggi regolari che voi non avete fatto. Quindi non puo' essere traccia d'esame per voi del corso B
Non ho la traccia della prova del 6 Giugno ma una simile.
Stabilire se L = { a^m b^n c^k : m = n, n, k > 0 } è libero da contesto.
Io l'ho risolto in questo modo:
L lo suddivido in : L1 = { a^m b^n : m = n, n > 0 } e L2 = { c^k : k > 0 } dove L = L1 x L2
L1 è un linguaggio di tipo 2 e le produzioni sono: S1--> ab | aS1b
L2 è un linguaggio di tipo 3 e le produzioni sono: S2--> c | cS2
L2 è di tipo 3,dunque per Chomsky qualunque linguaggio di tipo 3 piò essere rappresentato da un linguaggio di tipo 2,mentre L1 è di tipo 2 dunque la concatenazione è chiusa. Quindi L è libero da contesto.
Non ho la traccia della prova del 6 Giugno ma una simile.
Stabilire se L = { a^m b^n c^k : m = n, n, k > 0 } è libero da contesto.
Io l'ho risolto in questo modo:
L lo suddivido in : L1 = { a^m b^n : m = n, n > 0 } e L2 = { c^k : k > 0 } dove L = L1 x L2
L1 è un linguaggio di tipo 2 e le produzioni sono: S1--> ab | aS1b
L2 è un linguaggio di tipo 3 e le produzioni sono: S2--> c | cS2
L2 è di tipo 3,dunque per Chomsky qualunque linguaggio di tipo 3 piò essere rappresentato da un linguaggio di tipo 2,mentre L1 è di tipo 2 dunque la concatenazione è chiusa. Quindi L è libero da contesto.
Se mi aggiungi anke la gramatica di L siamo a posto