ciao, non conosco la traccia in questione...questa volta erano diverse tra i due corsi...quindi non so cosa sia con precisione X ne quale sia il linguaggio.
A senso direi che X* rappresentava tutte le possibili stringhe ottenibili con l'alfabeto dato nella traccia, inclusa la stringa vuota. Immagino che L(G) fosse lineare destro. Quindi la traccia diceva di scoprire se X*-L(G) fosse anche lineare destro. E questa la potevi risolvere, ad esempio, sfruttando la proprietà di chiusura delle operazioni.
ho un problema con il piano di studi: io ho dato programmazione quando si faceva il Pascal, e a Linguaggi si faceva il C. Linguaggi non l'ho ancora dato Con il nuovo piano di studi al Linguaggi si fa il C++. Cosa devo fare? Devo studiare il C o il C++?
Citazione:per ipotesi di induzione ogni stringa derivabile da S in n-1 passi è una parola di L e ne consegue che è nel seguente formato: w' = a^k b^k, k > 0
non mi è chiaro perchè si afferma che w' = a^n-1 b^n-1 da a^k S b^k derivato in k passi applicando la produzione 1 (k > 0)
A senso, se da S in k passi ottengo a^kb^k, in n-1 passi otterro' a^m-1 b^n-1
Poiche' dobbiamo dimostrare che da S in n passi ottengo una partola di L Poiche' da S in 1 passo ottengo aSb, ne restano n-1 passi da S (la S che si trova tra a e b dopo 1 paso) in n-1 passi ottengo a^n-1 b^n-1 posso riscrivere dicendo che da S in n passi ottengo a a^n-1 b^n-1 b che è proprio a^n b^n
si considera la stringa pompata uv^2wx^2y e si deve far vedere che appartiene a L...
in questo caso, visto che la sottostringa vwx è formata da sole a, aggiungerai solo un certo numero di a....quante?
siccome la parte che aumenta in lunghezza è la sottostringa vwx, al massimo ne aggiungi p (perche' vwx è lunga massimo p per la condizione 1) e al minimo ne aggiungi 1 (perche' vwx non puo' essere la parola vuota per la condizione 2). Quindi ne aggiungi un certo numero 0<t<=p.......e quindi la stringa pompata avra' p+t simboli a....
quindi nella stringa uvvwxxy(uv^2wx^2y), vwx è la mia sottostringa mentre uv(di sinistra) è a^p e uv(di destra) è b^p c^p ? E' giusto ?
In realta è proprio questo che non afferro...
comunque grazie per la risposta precedente
No....a priori non sappiamo quante a stanno in u, v, w o x.....e non ci interessa. Quello che conta è quanti simboli aggiungiamo pompando la stringa. Siccome hai supposto il primo caso, cioè vwx composto da sole a, aggiungerai sole a. Quante ne aggiungi? almeno 1 e massimo p per l,e due condizioni del pumping lemma.
Innanzitutto volevo ringraziarla del tempo che mi dedica...
Archiviata la questione delle sottostringhe mi si è presentato il problema delle dimostrazioni dove si ragiona sulla lunghezza di uvvwxxy.
L'esempio è l'esercizio a pag 4.3 del libro di Semeraro (pag. 98).
Prendiamo il linguaggio a^n^2 con n>=0 e quindi z=a^p^2 perciò risulta p^2>p da cui z=uvwxy con |vwx|<=p.
Il libro riporta |uvvwxxy|=|z|+|vx| <= |z|+|vwx|. Perchè ? E' evidente che la lunghezza della stringa pompata è |z|+|vx| ma, la disuguaglianza che significa ?
Ad intuito ho capito che p^2<|uvvwxxy|<(p+1)^2 non è vera perchè fra le stringa di lunghezza p^2 e quella successiva (p+1)^2 non c'è niente quindi a maggior ragione non c'è uvvwxxy; ma il procedimento per arrivare a (p+1)^2 non mi è chiaro. Cosa significano i passaggi intermedi ?
raga un consiglio da amico. non soffermatevi troppo sui primi capitoli. studiatevi bene i capitoli 5, 6 e 7 che sono i capitoli fondamentali. una volta che avete studiato BENE quei capitoli potete fare tutti gli esercizi che volete!!!
raga un consiglio da amico. non soffermatevi troppo sui primi capitoli. studiatevi bene i capitoli 5, 6 e 7 che sono i capitoli fondamentali. una volta che avete studiato BENE quei capitoli potete fare tutti gli esercizi che volete!!!
questo è un copnsiglio da NON seguire, visto che i primi capitoli vi danno tutte3 le definizioni necessarie per comprendere i capitioli successivi....
L'esempio è l'esercizio a pag 4.3 del libro di Semeraro (pag. 98).
Prendiamo il linguaggio a^n^2 con n>=0 e quindi z=a^p^2 perciò risulta p^2>p da cui z=uvwxy con |vwx|<=p.
Il libro riporta |uvvwxxy|=|z|+|vx| <= |z|+|vwx|. Perchè ? E' evidente che la lunghezza della stringa pompata è |z|+|vx| ma, la disuguaglianza che significa ?
|z|+|vx| <= |z|+|vwx| perche' |vx|<= |vwx| in quanto |w| potrebbe essere 0 o maggiore di 0....di conseguenza la disuguaglianza
Domande per il docente del corso B
Discussione Bloccata
Inserito il - 17/02/2006 : 09:57:38
