Morpheus_/_Neo
15-09-2005, 11:55
Ciao a tutti, sto preparando l'esame di Informatica Teorica e mi e' venuto un dubbio riguardante il lemma di Ogden.
Lemma: dato un linguaggio context-free L, esiste una costante n dipendente solo da L tale che se z appartiene a L e |z| >= n allora z = uvwxy e posso scegliere su z n o piu' posizioni in modo che
1. vx contiene almeno una posizione tra quelle scelte
2. vwx contiene al piu' n delle posizioni scelte
3. per ogni i u(v^i)w(x^i)y appartiene a L
Dubbio: come si dimostra il punto 2?????
grazie a tutti
M_/_N
Lemma: dato un linguaggio context-free L, esiste una costante n dipendente solo da L tale che se z appartiene a L e |z| >= n allora z = uvwxy e posso scegliere su z n o piu' posizioni in modo che
1. vx contiene almeno una posizione tra quelle scelte
2. vwx contiene al piu' n delle posizioni scelte
3. per ogni i u(v^i)w(x^i)y appartiene a L
Dubbio: come si dimostra il punto 2?????
grazie a tutti
M_/_N