| Autore |
 Discussione  |
|
|
xgeneralex
Utente giovane
Regione: Puglia
Prov.: Bari
Città: Bari
|
 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 
|
..siamo solo noi...generazione di sconvolti ke nn han + santi nè eroi...siamo solo noiiiiiiiiiiiiiiiiiii.... |
|
|
Domenicodattoma
Utente medio
Prov.: Bari
Città: Conversano
|
 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 |
E' impossibile sapere tutto. E' però possibile sapere sempre dove poter recuperare ogni genere di informazione. |
 |
|
|
celeste
Nuovo Utente
|
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. |
|
|
|
francesca
Utente assiduo
Regione: Puglia
Prov.: Bari
Città: Bisceglie
|
Inserito il - 12/06/2009 : 14:57:51
|
| che domande c'erano? |
|
|
|
celeste
Nuovo Utente
|
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
Utente assiduo
Regione: Puglia
Prov.: Bari
Città: Bisceglie
|
Inserito il - 12/06/2009 : 23:38:03
|
| e l'altra? |
|
|
|
titty2008
Utente giovane
|
Inserito il - 14/06/2009 : 11:37:45
|
| definire le principali funzioni dell'analizzatore lessicale |
|
|
|
francesca
Utente assiduo
Regione: Puglia
Prov.: Bari
Città: Bisceglie
|
Inserito il - 14/06/2009 : 18:13:51
|
 ok
|
|
|
|
xgeneralex
Utente giovane
Regione: Puglia
Prov.: Bari
Città: Bari
|
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.  |
..siamo solo noi...generazione di sconvolti ke nn han + santi nè eroi...siamo solo noiiiiiiiiiiiiiiiiiii.... |
|
|
|
celeste
Nuovo Utente
|
Inserito il - 15/06/2009 : 12:55:56
|
| Gentilmente qualcuno puo' inserire le soluzioni? |
Modificato da - celeste in data 15/06/2009 12:56:33 |
|
|
|
bono85
Utente giovane
Regione: Puglia
Prov.: Bari
Città: Putignano
|
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 |
|
|
| |
Discussione |
|
Qualcuno mi aiuta a risolvere questo esercizio?
