| Autore |
 Discussione  |
|
|
donatigno
Nuovo Utente
Regione: Puglia
Prov.: Bari
Città: Terlizzi
|
 Inserito il - 16/11/2010 : 11:56:02
|
Salve,
questo è l'esonero appena concluso, volevo avere dei confronti sullo svolgimento di questi 3 esercizi. Postate le soluzioni che per voi sono corrette!
1) Stabilire se il seguente linguaggio:
L={ba^ib^jc^k:0<i<=j<k}
è lineare destro, giustificando formalmente la risposta;
2) Sia dato il linguaggio:
L={b^2n : n>=0}
Determinalre il tipo di L, indicando il tipo più specifico nella gerarchia di Chomsky;
Fornire una grammatica generativa per il linguaggio L^2;
3) Sia dato il seguente linguaggio sull'alfabeto X={1,2,-}
L={1^n-2^n : n>0}
Definire una grammatica generativa per L;
|
Donato Grieco |
|
|
xgeneralex
Utente giovane
Regione: Puglia
Prov.: Bari
Città: Bari
|
Inserito il - 16/11/2010 : 18:59:04
|
il primo purtroppo non ho capito bene come risolverlo...mi piacerebbe sapere come l'hai svolto.
se si trovava un automa oppure se si usava il PL...boh...
il secondo ho trovato la grammatica per L e poi L2.
il terzo, ho diviso in due L quindi come 1^n - e 2^n...trovate le grammatiche(libere)ho trovato la g3 concatenazione...non so se è corretto però... |
..siamo solo noi...generazione di sconvolti ke nn han + santi nè eroi...siamo solo noiiiiiiiiiiiiiiiiiii.... |
 |
|
|
donatigno
Nuovo Utente
Regione: Puglia
Prov.: Bari
Città: Terlizzi
|
Inserito il - 16/11/2010 : 21:24:45
|
Al primo bisognava applicare il pumping lemma per i linguaggi regolari.
Il terzo dovrebbe essere :
P=
{
S->1A2
A->1A2 | -
}
peccato ho realizzato solo dopo
Per il secondo esercizio ,come si componeva L^2? Si applicava qualche regola di chiusura? |
Donato Grieco |
|
|
|
mago
Utente giovane
|
Inserito il - 17/11/2010 : 12:44:00
|
Il primo l'ho "fatto" (virgolette perchè non completo) con il PL linguaggi regolari.
Il secondo ho suddiviso il linguaggio in b^n concatenato b^n. Il quadrtato sarebbe sarebbe il quadrato di questa concatenazione. Quindio trovato la grammatica come concatenazione.
Il terzo generando la grammatica S->1A, A->-B, B->2B|2. Questo perchè 1^n è sempre 1. "Provando" la gramatica funziona. (le parole sarebbero 1-2, 1-4, 1-8, 1-16, ...). |
|
|
|
xgeneralex
Utente giovane
Regione: Puglia
Prov.: Bari
Città: Bari
|
Inserito il - 17/11/2010 : 18:16:55
|
mago purtroppo è errato, ed è giusto donatigno, all'esercizio 3 le produzioni erano del tipo:
11A22,111A222,1111-2222....etc etc etc...
quindi la grammatica corretta è S->1A2;A->1A2|-...è tutta la giornata che mi mangio le mani, perchè purtroppo non mi è venuta questa intuizione durante lo scritto, ed erano ben 8 punti(quasi un punto a lettera nella grammatica :)). Il metodo,come ho fatto io, non va bene perchè altrimenti si perderebbe traccia delle a^n e b^n...che dispiacere... |
..siamo solo noi...generazione di sconvolti ke nn han + santi nè eroi...siamo solo noiiiiiiiiiiiiiiiiiii.... |
|
|
|
Donata Brazof
Nuovo Utente
|
Inserito il - 08/02/2011 : 19:03:46
|
il terzo esercizio
L={1^n-2^n : n>0}
semplicemente P: { S -> 1-2 | 1S2 } senza scomodare NT in più =)
|
|
|
| |
Discussione |
|
Appello 16/11/2010
