Newsgroup: it.scienza.informatica
Titolo: Generare una grammatica

Salve
data una lunga sequenza di frasi scritte usando una grammatica
CF incognita è possibile risalire in qualche modo in maniera
automatica alla grammatica che le ha generate ?
Grazie
--
_-==.==-_*_-==.==-_
  _    _   __    _   " Ogni sistema ha le sue leggi :
 |_)_ |_) (_  _ |_)     alcune possono essere eluse
 | (_|| \o__)(/_| \    altre...infrante " (Morpheus)
 (Giacomo Bellucci)
 
PaR._IL_BIAN...@libero.it
     _________
    /ficm code\          Per rispondermi togliete
    \ [Hx23B] /        _IL_BIANCONIGLIO_ dall'email
     ¯¯¯¯¯¯¯¯¯

Grazie
Mi spiace dare una risposta poco esauriente, ma ricordo solo di aver
indagato diverso tempo fa sull'argomento giungendo alla conclusione
che quello che vuoi fare e' un vero casino. Ricordo solo di aver letto
delle cose che mi avevano spinto ad abbandonare l'idea. Credo,
peraltro, che il suddetto problema sia ancora oggetto di ricerca visto
che offrono ricerche per dottorandi proprio su questo tema.
Ciao,
	Giuliano

automatica alla grammatica che le ha generate ?
Penso proprio di no. Le possibilita' sarebbero infinite!
-- 
Linux Registered User #181013
[Exokernels] Although one approach to eliminating bloated, buggy,
unreliable operating systems is to make them smaller, a more radical
one is to eliminate the operating system altogether.

 automatica alla grammatica che le ha generate ?
no, e anche se vai a tentativi genereresti sono un suo sotto insieme o un
equivalente di un suo sottoinsieme (fa conto che potrebbero esistere
infinite realizzazioni)
-- 
| /
| \Byte - Andrea Briganti - kbytesys(aaattt)
tiscali.it
CSLug member: 
http://cslug.linux.it
 - JID: 
kb...@jabber.linux.it
***Un giorno forse gli uomini saranno in grado di comprendersi

 Giuliano
Potresti darmi qualche indirizzamento per compiere una ricerca simile alla
tua ?
Grazie
--
_-==.==-_*_-==.==-_
  _    _   __    _   " Ogni sistema ha le sue leggi :
 |_)_ |_) (_  _ |_)     alcune possono essere eluse
 | (_|| \o__)(/_| \    altre...infrante " (Morpheus)
 (Giacomo Bellucci)
 
PaR._IL_BIAN...@libero.it
     _________
    /ficm code\          Per rispondermi togliete
    \ [Hx23B] /        _IL_BIANCONIGLIO_ dall'email
     ŻŻŻŻŻŻŻŻŻ

infinite realizzazioni)
Che ci sarebbero infinite realizzazioni è vero.
A questo punto la questione diventa:
"Esiste ed è unica la grammatica minimale che la genera?"
"E' possibile risalirvi?"

"E' possibile risalirvi?"
Scusa la banalita', ma la risposta non sarebbe "la grammatica minimale
e' la grammatica che genera solo quelle frasi"?


 e' la grammatica che genera solo quelle frasi"?
Potremmo definire la minimalità rispetto al numero di simboli
che servono per scrivere la grammatica.
--
_-==.==-_*_-==.==-_
  _    _   __    _   " Ogni sistema ha le sue leggi :
 |_)_ |_) (_  _ |_)     alcune possono essere eluse
 | (_|| \o__)(/_| \    altre...infrante " (Morpheus)
 (Giacomo Bellucci)
 
PaR._IL_BIAN...@libero.it
     _________
    /ficm code\          Per rispondermi togliete
    \ [Hx23B] /        _IL_BIANCONIGLIO_ dall'email
     ¯¯¯¯¯¯¯¯¯


che servono per scrivere la grammatica.
Se noi abbiamo n frasi f1, f2, ..., fn
la grammatica "minima" non e' forse la grammatica seguente?
G = < V, Sigma, P, S >
con V = {S}
Sigma = insieme dei simboli terminali delle frasi
S = simbolo iniziale
P = {S --> fk : per ogni k=1, ..., n}
G possiede il numero minimo di simboli.
Cioe' la soluzione alla domanda "qual e' la grammatica minimale" mi
sembra scontata, come gia' dicevo, ma non risolve il problema posto
all'apertura del thread.
Comunque io sono della stessa idea di Kbyte, un linguaggio finito di
parole si puo' generare in qualunque modo.
Forse varrebbe piu' la pena chiedersi "elencate tutte le parole di un
linguaggio, e' possibile ricavare la grammatica che genera tale
linguaggio con n simboli non terminali e m produzioni?"
Ciao


 all'apertura del thread.
Per numero di simboli intendevo i "simboli" necessari per scrivere la
grammatica in un qualche
formalismo (ad es BNF). Sicuramente quella che proponi non è minimale in tal
senso.


senso.
Puo' darsi, visto che forse stiamo intendendo cose diverse col termine
"simbolo".
Io sostengo semplicemente che secondo le definizioni di [1], data una
collezione di parole, la grammatica che le genera con:
- minor numero di variabili
- minor numero di simboli terminali
e' banalmente la grammatica che avevo descritto. Ovvero non puo'
esistere una grammatica con un minor numero di variabili e/o simboli
terminali che generi tale collezione. Ma d'altronde sto dicendo in
modo complicato una cosa ovvia: se mancasse un simbolo terminale, le
parole con tale simbolo non potrebbero essere generate.
Rif.:
[1] "The objects corresponding to syntactic categories we call 'non
terminals' or 'variables'....The objects which play the role of words
we shall call 'terminals'."
...
"Formally, we denote a grammar G by (V_N, V_T, P, S). The SYMBOLS V_N,
V_T, P and S are, respectively, the /variables, terminals, productions
and start symbol/. V_N, V_T and P are finite sets."
(Hopcroft, Ullman - "Formal Languages and their relation to aytomata")


 e non terminali (variabili) definiti nei linguaggi formali [1]?
Esempio :
Se la grammatica č
S=Sa|b
allora i "simboli" per scriverla sono [S,=,S,a,|,b] quindi sono 6.
Minimale in questo senso č sicuramente "piů minimale" che nel tuo :))
--
_-==.==-_*_-==.==-_
  _    _   __    _   " Ogni sistema ha le sue leggi :
 |_)_ |_) (_  _ |_)     alcune possono essere eluse
 | (_|| \o__)(/_| \    altre...infrante " (Morpheus)
 (Giacomo Bellucci)
 
PaR._IL_BIAN...@libero.it
     _________
    /ficm code\          Per rispondermi togliete
    \ [Hx23B] /        _IL_BIANCONIGLIO_ dall'email
     ŻŻŻŻŻŻŻŻŻ