| V I S U A L I Z Z A D I S C U S S I O N E |
| xgeneralex |
Inserito il - 06/06/2009 : 11:09:08
Buongiorno Ragazzi
non riesco a risolvere questo esercizio:
Dato L:{a^n b a^3n :n>0}
Dimostrare formalmente che L NON è LINEARE DESTRO.
Quindi io penso che si dimostri che non è LD tramite lo svolgimento del Pumping lemma per i linguaggi Regolari...Solo che dal libro non ho ben capito come si applica il tutto...C'è qualcuno che mi aiuta a svolgere questo esercizio. Vi ringrazio in anticipo per un'eventuale risposta  |
| 10 U L T I M E R I S P O S T E (in alto le più recenti) |
| bono85 |
Inserito il - 15/06/2009 : 13:43:36
Citazione:
Messaggio inserito da celeste
L={a^n b^k c^s| 0<n<=k<=s} Stabilire formalmente se è libero da contesto.
L={(abc)^n:n<=0} definire con una grammatica generativa o una macchina per il riconoscimento il linguaggio X*-L.
Il primo si risolve con il Pumping lemma dei linguaggi liberi.
Il secondo rendendosi conto che X*-L=Lcomplemento..... e quindi io mi sono trovato la G lineare destra,poi l'autome per L e poi l'automa per Lcomplemento |
| celeste |
Inserito il - 15/06/2009 : 12:55:56
Gentilmente qualcuno puo' inserire le soluzioni? |
| xgeneralex |
Inserito il - 15/06/2009 : 10:47:14
Citazione:
Messaggio inserito da Domenicodattoma
Il ragionamento è il seguente:
Supponiamo che L sia regolare. Deve quindi valere il relativo....
Spero di esser stato chiaro, ma soprattutto di non aver sbagliato niente...:D
Grazie mille Domenico! Mi sei stato molto Utile.  |
| francesca |
Inserito il - 14/06/2009 : 18:13:51
 ok
|
| titty2008 |
Inserito il - 14/06/2009 : 11:37:45
definire le principali funzioni dell'analizzatore lessicale |
| francesca |
Inserito il - 12/06/2009 : 23:38:03
e l'altra? |
| celeste |
Inserito il - 12/06/2009 : 16:46:35
L={a^n b^k c^s| 0<n<=k<=s} Stabilire formalmente se è libero da contesto.
L={(abc)^n:n<=0} definire con una grammatica generativa o una macchina per il riconoscimento il linguaggio X*-L. |
| francesca |
Inserito il - 12/06/2009 : 14:57:51
che domande c'erano? |
| celeste |
Inserito il - 12/06/2009 : 13:54:35
Qualche anima buona potrebbe postare perfavore le soluzioni dello scritto del 10,esercizi 1 e 3 ??? spero in una risposta. |
| Domenicodattoma |
Inserito il - 09/06/2009 : 18:23:06
Il ragionamento è il seguente:
Supponiamo che L sia regolare. Deve quindi valere il relativo Pumping Lemma, e quindi si deve poter dire che data una parola del linguaggio di lunghezza maggiore o uguale ad N (|z|>=n), e dato un automa M con N stati tale che L=T(M), z si può scrivere come uvw, e uv*w è elemento di T(M).
Prendiamo ora la parola z=a^n b a^3n di lunghezza 4N+1>N.
Dato che la lunghezza della parola supera il numero di stati dell'automa, è evidente che nel percorso di riconoscimento due stati (che indicheremo con qi e qj) saranno coincidenti, andando a creare un ciclo. Evidentemente questo ciclo avverrà durante il riconoscimento delle 'a' iniziali, e quindi potremo aggiungere un certo numero di 'a' (propriamente pari a j-i) quante volte vorremo senza alterare l'esito del riconoscimento, ma ledendo il vincolo della forma di frase. Dato che queste nuove parole non fanno parte del linguaggio ma sono accettate dall'automa si giunge ad un assurdo. L'assurdo deriva dall'aver supposto L regolare. Dunque L non è un linguaggio regolare.
Spero di esser stato chiaro, ma soprattutto di non aver sbagliato niente...:D |
