[Informatica Teorica] Disambiguare una grammatica
Salve a tutti, è da un po che sto cercando di risolvere il seguente problema:
"Dimostrare che la seguente grammatica è ambigua e determinarne una equivalente non ambigua"
A -> aB | B
B -> Bc | b | ab
dimostro che la grammatica è ambigua facendo vedere due derivazioni diverse per la stringa "ab"
A => aB => ab
A => B => ab
e adesso dovrei determinare una grammatica non ambigua equivalente.. sapreste dirmi se esiste un algoritmo per farlo? o nel caso darmi un piccolo aiuto per partire?
grazie
"Dimostrare che la seguente grammatica è ambigua e determinarne una equivalente non ambigua"
A -> aB | B
B -> Bc | b | ab
dimostro che la grammatica è ambigua facendo vedere due derivazioni diverse per la stringa "ab"
A => aB => ab
A => B => ab
e adesso dovrei determinare una grammatica non ambigua equivalente.. sapreste dirmi se esiste un algoritmo per farlo? o nel caso darmi un piccolo aiuto per partire?
grazie
Risposte
Ciao HeroGian 
Il primo punto riguardo all'ambiguità della grammatica tramite l'esempio è ok. Unico fatto, ad essere proprio precisi e rigorosi, bisogna sapere che il simbolo iniziale della grammatica data è $A$.
Per il secondo punto in realtà non esiste un vero e proprio algoritmo. Il passo iniziale è comunque quello di capire che linguaggio genera questa grammatica osservando bene le produzioni. Una volta capito quello è sufficiente riscrivere le produzioni in maniera appunto non ambigua.
Vedrai che passo passo puoi arrivare la soluzione senza molte difficoltà. Come sempre per ogni dubbio sono qui (pian piano ti posso guidare alla soluzione).
Il primo punto riguardo all'ambiguità della grammatica tramite l'esempio è ok. Unico fatto, ad essere proprio precisi e rigorosi, bisogna sapere che il simbolo iniziale della grammatica data è $A$.
Per il secondo punto in realtà non esiste un vero e proprio algoritmo. Il passo iniziale è comunque quello di capire che linguaggio genera questa grammatica osservando bene le produzioni. Una volta capito quello è sufficiente riscrivere le produzioni in maniera appunto non ambigua.
Vedrai che passo passo puoi arrivare la soluzione senza molte difficoltà. Come sempre per ogni dubbio sono qui (pian piano ti posso guidare alla soluzione).
Ciao, grazie mille per la risposta!
ho provato a ragionare un po sulle produzioni della grammatica:
da quello che ho notato il linugaggio generato dalla grammatica dovrebbe essere questo:
"tutte le stringhe su {a, b, c} che possono iniziare con una 'a', seguite da una 'b' oppure da un 'ab' e terminate con un numero arbitrario di c"
quindi sotto forma di espressione regolare dovrebbe essere così: (a | eps)(b | ab)c*
poi per la grammatica ho provato ad eliminare la produzione A -> ab che dava problemi.. ma togliendo quella non potevo più generare ad esempio la stringa aabc, quindi ho aggiunto la produzione A -> aaB, infine la grammatica finale dovrebbe essere:
A -> aB | aaB
B -> Bc | b
ho provato a ragionare un po sulle produzioni della grammatica:
da quello che ho notato il linugaggio generato dalla grammatica dovrebbe essere questo:
"tutte le stringhe su {a, b, c} che possono iniziare con una 'a', seguite da una 'b' oppure da un 'ab' e terminate con un numero arbitrario di c"
quindi sotto forma di espressione regolare dovrebbe essere così: (a | eps)(b | ab)c*
poi per la grammatica ho provato ad eliminare la produzione A -> ab che dava problemi.. ma togliendo quella non potevo più generare ad esempio la stringa aabc, quindi ho aggiunto la produzione A -> aaB, infine la grammatica finale dovrebbe essere:
A -> aB | aaB
B -> Bc | b
Il linguaggio generato dalla tua grammatica che hai determinato è corretto. A dire la verità quando l'avevo determinato io facendomi l'esercizio su carta l'avevo scritto come $L = \{(\epsilon + a + aa)bc^{\star}\}$ ma come sicuramente noterai è del tutto equivalente a quello che hai riportato.
La grammatica non ambigua non è però ancora del tutto corretta perché nelle tue produzioni scritte così imponi che le varie stringhe del linguaggio debbano necessariamente iniziare per $a$ quando invece non è così.
PS: utilizza pure il codice LaTeX per scrivere le formule in maniera più ordinata
.
La grammatica non ambigua non è però ancora del tutto corretta perché nelle tue produzioni scritte così imponi che le varie stringhe del linguaggio debbano necessariamente iniziare per $a$ quando invece non è così.
PS: utilizza pure il codice LaTeX per scrivere le formule in maniera più ordinata
.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo