Newsgroup: it.comp.ia
Titolo: Grammatica di tipo 0, cos'e' ?

Che differenza c'e' tra una Grammatica di tipo 0,
e una grammatica di tipo 1,
ecc...
Ringrazion in anticipo a chi mi rispondera
saluti
davide U

 wrote in message 8j9uir$3s4$1...@nslave1.tin.it...

Immagino che tu ti riferisca alla Gerarchia di Chomsky dove le G di tipo 0
(Unrestricted Grammars) rappresentano i linguaggi ricorsivamente enumerabili
mentre le G di tipo 1 (Context Sensitive Grammars) rappresentano i linguaggi
sensibili al contesto. Le G0 possono essere rappresentate solo da una
Macchina di Turing, le G1 da un Automa Linear-Bounded (cioč da una TM a
nastro finito lungo kn dove n č la lunghezza dell'input e k una costante
dipendente dall'Automa specifico).
Cmq se fai una ricerca per "Chomsky Hierarchy" su Google o Altavista
dovresti trovare un bel po' di link.
Scusa la mia ignoranza (in questo NG sono solo uno spettatore e da poco
tempo) ma per cosa si usano le FLG nell'AI ? Forse per il riconoscimento dei
linguaggi naturali ? In questo caso *credo* che un linguaggio naturale debba
avere una G0 e non una G1.
Ciao


grazie


Tra l'altro oltre alle G0 e alle G1 esistono anche le G2 e le G3. Le
G2 sono le ghrammatiche libere dal contesto, mentre le G3
(particolarmente interessanti) sono le regular gramamrs.
In pratica le uniche produzioni consentite nelle G3 sono del tippo :
S->a oppure S->ba
dove a appartienne a T star mentre b appartiene semplicemente a N
In pratica in questo tipo di grammatica si puo' introdurre al massimo
sono un simbolo non terminale a produzione
Augusto Pucci
Webmaster di Prospektiva On-line
http://www.prospektiva.it


Non so darti una risposta in due parole. Diciamo che, poco formalmente, una
G0 (e quindi i linguaggi che essa può riconoscere) ha regole di derivazione
molto "permissive" ovvero è sufficiente che nella derivazione A -> B, ci sia
l'unica restrizione che A non sia vuota (A e B sono stringhe qualunque del
vocabolario del linguaggio). G1, G2 e G3 sono via via sempre più restrittive
nelle regole di derivazione (G2 e G3 sono rispettivamente le Grammatiche
Context-Free e Regolari).
Per esempio, le G1 che hanno regole di derivazione nella forma mAn -> mBn, B
(che è nella parte destra della derivazione) non può essere vuota (mentre m
ed n possono esserlo). Chiaramente le G0 sono le più espressive tra le
grammatiche, ma proprio per questo sono anche le più difficili da trattare
da un punto di vista computazionale e non sono utilizzate nei linguaggi di
programmazione.
Inoltre, il problema dei linguaggi ricorsivamente enumerabili è che se la
stringa di input non appartiene al linguaggio, invece di essere rifiutata,
può condurre la TM ad un loop infinito (cosa che non accade per i linguaggi
detti ricorsivi che sono un loro sottoinsieme).
Non so se questo ti può aiutare, ma io conosco la materia solo dal punto dei
linguaggi "artificiali" che si limitano alle G3 per l'analisi lessicale e G2
per l'analisi sintattica (anche se esistono strutture Context-sensitive
anche nei liguaggi di programmazione) e sui libri che ho letto le G0 vengono
citate solo per completezza.
Ciao
PS: un mio collega mi dice che gli sembra che alcune lingue (ma non
l'italiano) possano essere G1, ma non si ricorda qual'è la discriminante

 [Ling. Naturali solo con G0] 
Anche io ero convinto di questo, olo che ho riflettuto sul fatto che in
realta` ogni macchina di calcolo reale e` una LBA quindi
il linguaggio naturale deve poter essere riconosciuto con una LBA cioe`
deve essere necessariamente di tipo 1. Mi sbaglio?
 
--
Roberto Corda,

 wrote:

Non vorrei sbagliarmi am mi sembra di aver letto...che si e' context
sensitive..il che mi sembra anche coerente



Non ho sotto mano gli appunti dell'universita' quindi non posso darti una
definizione stringente, comunque se ti accontenti di una definizione 'a spanne'
si puo' dire che:
un insieme e' RICORSIVAMENTE NUMERABILE quando i suoi elementi possono essere
messi in corrispondenza con i numeri naturali, in pratica quando puoi contarli
uno, due, tre, etc. senza pero' che sia richiesta la terminazione del conteggio.
gli insiemi RICORSIVI, invece, sono quegli insiemi ricorsivamente numerabili in
cui il conteggio termina.
So che forse una definizione cosi' semplicistica fara' rabbrividire i puristi,
ma questi dovrebbero essere i due concetti base. magari se recupero gli appunti
dell'universita' ti posto una definizione piu' formale.
Magari se vivi o capitina Milasno o conosci qualcuno che vi studia puoi
procurarti gli appunti del corso di Metodi per il Trattamento dell'Informazione
del prof Bertoni, o di Linguaggi Formali e Compiolatori della prof.ssa Bandini.
Sono entrambi chiarissimi, a dir poco.
HTH
Carlo


I linguaggi ricorsivamente enumerabili sono insiemi ( eventualmente
infiniti) di stringhe che possono essere prodotte secondo un ordine ( detto
canonico) da una macchina di Turing. In pratica sono "numerabili", nel senso
che gli elementi del linguaggio sono in corrispondenza biunivoca con i
numeri naturali. E questo e' quanto. La numerabilita' non implica che le
stringhe che non appartengono al linguaggio possano essere distinte in un
tempo finito da quelle che vi appartengono, cosi' che se sottoponiamo ad una
TM una stringa di un linguaggio r.e. siamo certi che la computazione
terminera' con un riconoscimento, mentre se le sottoponiamo una stringa non
appartenente al linguaggio la computazione potrebbe non terminare mai. I
linguaggi ricorsivi sono un sottoinsieme dei linguaggi r.e., in quanto
numerabili, ma in questo caso il riconoscimento in tempo finito degli
elementi non appartenenti al  linguaggio e' assicurato.
Anders

 deve essere necessariamente di tipo 1. Mi sbaglio?
Non conosco abbastanza la teoria dei linguaggi naturali per poter
rispondere. Se qualcuno ha una risposta sarei interessato a conoscerla.
Franco

 Sono entrambi chiarissimi, a dir poco.
Sai dirmi come posso procurarmeli ? Vivo a Milano, ma sono fuori
dall'ambiente universitario.
Franco

Credo che le copisterie della zona di Citta'Studi siano pieni di appunti dei
corsi di Scienze dell'Informazione.
Credo che in CLUED o CUSL vicino alla segreteria di Scienze MMFFNN in via
celoria abbiano ancora gli appunti del corso di bertoni.
Altrimenti potresti trovare entrambi in qualche copisteria vicino a Via
Comelico (Viale umbria... altezza mercato comunale) visto che ci si e'
trasferita da qualche hanno la facolta' di informatica.
Chiedo umilmente scusa agli altri lettori, non volevo fare pubblicita' di
alcun tipo, ma dopo aver fatto gli esami con Bertoni e la Bandini mi sono
accorto di aver imparato parecchio (specialmente perche' l'esame di Bertoni
lo avevopreparato col mio vero prof che sara' un genio lui ma per spiegare FA
CAGARE!!!! La legge sulla privacy mi impedisce di farne il nome) .
HTH
    Carlo


non sono un esperto...
Quando puoi elencare un insieme mettendone in relazione biunivoca gli 
elementi con i numeri interi (cioe', ad un unico elemento corrisponde un 
solo numero), quell'insieme e' numerabile. Intutiviamente, l'insieme e' 
potenzialmente non-finito, ma discreto - non denso come i razionali o 
continuo come i reali, ed e' possibile costruirci una sequenza - cioe' 
partire da un "elemento 0" e andare avanti fino a trovare l'"elemento n-
esimo" per qualunque n, a patto di aspettare a sufficienza.
Ora, se la relazione biunivoca e' una funzione computabile ricorsiva, 
l'insieme e' ricorsivamente enumerabile. Una delle conseguenze della tesi 
di Church e' che un insieme numerabile e' r.e e viceversa.
-- 
God is Real, unless declared Integer.
ObjectZone - 
http://space.tin.it/computer/csadun

rispondere. Se qualcuno ha una risposta sarei interessato a conoscerla.
L'e' che non si sa. :) Quanto sopra ad esempio e' una conseguenza 
dell'ipotesi di computabilita', ma nessuno ci dice che l'ipotesi e' 
verificata (anche se si puo' mostrare che non ci sono ostacoli di 
principio).
Tieni anche presente che - per computazioni reali - il vero limite e' 
spesso la trattabilita'. In NL "forte" si lavora pensando che l'italiano, 
per dire, sia di tipo 1, e cercando un modello di computazione di 
complessita' accettabile.


 alcun tipo
Non so se è pubblicità, ma mi sembrano fatti bene e possono essere un buon
punto di partenza per chi è interessato all'argomento.
Cmq, grazie 1000.
[fine]


ciao