Newsgroup: it.scienza.informatica
Titolo: Linguaggio libero

Salve,
non ho capito la seguente cosa.
Si consideri il linguaggio L = { a^n b^n c^i | n>=1 e i>=0}.
Il mio libro mi dice che è libero dal contesto, e da una grammatica
libera che lo
genera.
Però, se io uso il teorema "uvwxy", non mi tornano i conti. Infatti, il
teorema dice:
     Sia L un linguaggio generato da una Grammatica Lineare.
     Esiste una costante p, dipendente solo da L, tale che se esiste
     una parola z di L, con |z|>p, allora z può essere scritta come
     z=uvwxy, dove |vwx| <= p e vx non è la stringa vuota, in modo tale
     che u(v^i)w(x^i)y appartiene ancora ad L, i = 0,1,2....
Supponiamo L libero. Sia p la costante del teorema precedente.
Se io scelgo n = p e i = 0 allora ok, riesco a trovare sempre una
partizione
per parole di lunghezza > p. Ma, se io scelgo n = p e i = p, ottengo
una parola z con |z| > p sicuramente e per la quale non ho nessuna
partizione. Infatti
z = (a^p)(b^p)(c^p). Come diavolo è allora che il libro mi dice che è un
linguaggio
libero?
Grazie e ciao.

 z = (a^p)(b^p)(c^p).
E' questa la parte che non funziona. Tu non puoi "scegliere n=p e i=0" o cose
del genere. Il tuo linguaggio e' definito per qualunque valore di n>=1 e
qualunque valore di i>=0. Scegliere un valore per n e uno per i significa
definire una data stringa. D'altro canto la p del teorema e' una costante che
dipende dal linguaggio. Nel caso specifico p vale 4. A questo punto il teorema,
applicato al tuo linguaggio, si legge (rinomino la i del teorema in j per non
confonderla con quella del linguaggio):
Qualunque parola z appartenente a L e tale che |z|>4 puo' essere scritta come
uvwxy dove |vwx|<=4 e vx non e' vuota e u(v^j)w(x^j)y (con j = 0,1,2....)
appartiene ancora a L.
Per comodita' notiamo che L lo possiamo anche definire come l'insieme delle
stringhe S(n,i) dove appunto S(n,i)=a^n b^n c^i, n>=1 e i>=0
Ora e' evidente che
|S(n,i)| = 2n+i, n>=1 e i>=0
e che le stringhe che hanno lunghezza maggiore o uguale a 4 (quelle che contano
per il teorema) possono essere di due soli tipi:
S(1,i), i>=2
S(n,i), n>=2 e i>=0
mentre le stringhe S(1,0) e S(1,1), pur appartenenti a L, non sono lunghe
abbastanza da soddisfare la prima condizione del teorema.
Vediamo separatamente i due casi:
Ciascuna stringa z=S(1,i), i>=2 puo' essere scritta come uvwxy ponendo (nota: £
rappresenta epsilon, la stringa vuota):
u=ab
v=c
w=£
x=c
y=c^(i-2)
Dove |vwx|<=4 e vx non e' vuota.
Ed e' facile dimostrare che "u(v^j)w(x^j)y" si riduce a "ab (cc)^j c^(i-2)" che
corrisponde a S(1,2j+i-2). Con i che e' quella usata per la stringa z e j>=0.
Essendo i>=2 e j>=0 abbiamo che 2j+i-2 >= 0 che e' un dominio valido per il
secondo parametro di S nel linguaggio.
Nell'altro caso ciascuna stringa z=S(n,i), n>=2, i>=0 puo' essere scritta come
uvwxy ponendo:
u=a^(n-1)
v=a
w=£
x=b
y=b^(n-1) c^i
Dove |vwx|<=4 e vx non e' vuota.
Ed e' facile dimostrare che "u(v^j)w(x^j)y" si riduce a "a^(n-1) a^j b^j b^(n-1)
c^i" che corrisponde a S(j+n-1,i). Con i e n che sono quelle usate per la
stringa z e j>=0. Essendo n>=2 e j>=0 abbiamo che j+n-1 >= 1 che e' un dominio
valido per il primo parametro di S nel linguaggio.
--
Andrea Ferro
---------
Brainbench C++ Master. Scored higher than 97% of previous takers
Scores: Overall 4.46, Conceptual 5.0, Problem-Solving 5.0
More info 
http://www.brainbench.com/transcript.jsp?pid=2522556

 ..............
Ti ringrazio molto per la lunga risposta! Domani le darň uno sguardo piů
approfondito di
quanto non possa fare ora (ore 0:40)!
Ciao.

 Questo mi interessa. Come hai fatto a calcolarlo?
Il fatto che la p dipenda dal linguaggio l'ho detto perche' fa parte del teorema
(che ho preso per buono ma ovviamente suppongo esista una dimostrazione dello
stesso).
Per il calcolo mi sono basato sul fatto che, stando al teorema, se la cosa vale
per un p=k allora vale anche per un p>=k. Ergo quello che conta e' il minimo
valore di p. Per calcolare il 4 non ho usato nessun procedimento rigoroso.
Semplicemente con p=4 posso dimostrare che il teorema si applica al linguaggio
(non in maniera rigorosa ma semplicemente trovando in maniera empirica dei
valori che lo soddifano) e non sono riuscito a trovare tali valori per le
(poche) stringhe del linguaggio con lunghezza inferiore a 4!
Come vedi ... anche senza ricordare quasi nulla della teoria ho almeno risolto
il tuo dubbio principale. Ma da questo a darti una lezione teorica ... ce ne
passa!
