| V I S U A L I Z Z A D I S C U S S I O N E |
| donatigno |
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;
|
| 5 U L T I M E R I S P O S T E (in alto le più recenti) |
| Donata Brazof |
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ù =)
|
| xgeneralex |
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... |
| mago |
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, ...). |
| donatigno |
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? |
| xgeneralex |
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ò... |
