[LF] determinare una grammatica che genera un ling.
Ciao a tutti!
Ho da poco iniziato a studiare questa (per me splendida) materia, vorrei sapere se c'è un metodo per determinare, dato un linguaggio, la grammatica che lo genera?
Perché fino ad ora io sono andato ad intuito e ho notato che per linguaggi semplici riesco a trovare una grammatica abbastanza agevolmente mentre per linguaggi anche solo un po' più complessi le cose si complicano, sopratutto perché, si sa, all'esame il tempo non è infinito infatti l'esercizio riesco anche a risolverlo ma impiegando un po' di tempo.
Ad esempio prendendo il linguaggio delle parentesi ben formate riesco a trovare una grammatica
$G={X, V, S, P}$
dove $X$ è l'insieme dei terminali $X={(,)}$
$V$ l'insieme dei $NT$ $V={S}$
$S$ è il simbolo iniziale
e $P={S->(), S->(S)}$ sono le produzioni.
Tuttavia questo è un esempio direi banale, quindi con un po' di logica ci si arriva immediatamente mentre per linguaggi un po' più complicati come dovrei procedere?
Ringrazio tutti anticipatamente, e mi scuso per la lunghezza del post
Ho da poco iniziato a studiare questa (per me splendida) materia, vorrei sapere se c'è un metodo per determinare, dato un linguaggio, la grammatica che lo genera?
Perché fino ad ora io sono andato ad intuito e ho notato che per linguaggi semplici riesco a trovare una grammatica abbastanza agevolmente mentre per linguaggi anche solo un po' più complessi le cose si complicano, sopratutto perché, si sa, all'esame il tempo non è infinito infatti l'esercizio riesco anche a risolverlo ma impiegando un po' di tempo.
Ad esempio prendendo il linguaggio delle parentesi ben formate riesco a trovare una grammatica
$G={X, V, S, P}$
dove $X$ è l'insieme dei terminali $X={(,)}$
$V$ l'insieme dei $NT$ $V={S}$
$S$ è il simbolo iniziale
e $P={S->(), S->(S)}$ sono le produzioni.
Tuttavia questo è un esempio direi banale, quindi con un po' di logica ci si arriva immediatamente mentre per linguaggi un po' più complicati come dovrei procedere?
Ringrazio tutti anticipatamente, e mi scuso per la lunghezza del post
Risposte
"_overflow_":
vorrei sapere se c'è un metodo per determinare, dato un linguaggio, la grammatica che lo genera?
Qual è la difficoltà? Considera che in genere non è così difficile...
Se hai fatto un po' di esercizi puoi provare a fare (o anche solo a figurarti) l'automa associato.
Ciao, intanto grazie per avermi risposto.
Si lo so che non è un'operazione così difficile, quello che mi chiedevo è se c'è una sorta di algoritmo per determinare la grammatica di un linguaggio, o semplicemente si deve andare ad intuito?
PS: di automi associati alle grammatiche non abbiamo ancora parlato.
Si lo so che non è un'operazione così difficile, quello che mi chiedevo è se c'è una sorta di algoritmo per determinare la grammatica di un linguaggio, o semplicemente si deve andare ad intuito?
PS: di automi associati alle grammatiche non abbiamo ancora parlato.
Un algoritmo per passare da una definizione ad una grammatica... mi sembra un po' tortuoso, dovrebbe esserci un modo univoco di definire un linguaggio ed usualmente questo è proprio la grammatica stessa.
Comunque se esiste un algoritmo del genere non ne ho mai sentito parlare. Bisognerebbe consultare TAOCP: se esiste, lì c'è.
Invece con l'automa, sopratutto se (come è usuale) ne fai una rappresentazione grafica, è molto semplice; in questo caso ci sono algoritmi che trasformano un automa in grammatica e viceversa. Per classi di linguaggi 3 e 2, regolari e liberi da contesto, ovviamente.
Comunque se esiste un algoritmo del genere non ne ho mai sentito parlare. Bisognerebbe consultare TAOCP: se esiste, lì c'è.
Invece con l'automa, sopratutto se (come è usuale) ne fai una rappresentazione grafica, è molto semplice; in questo caso ci sono algoritmi che trasformano un automa in grammatica e viceversa. Per classi di linguaggi 3 e 2, regolari e liberi da contesto, ovviamente.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo