Grammatica Context-Free
Sia L il linguaggio su alfabeto = {a,b} delle parole di lunghezza dispari che contengono aba esattamente al centro delle parole stesse
la seguente grammatica è corretta?
S->A
A->abAab
A->baAba
A->aAa
A->bAb
A->aba
A->Epsilon
la seguente grammatica è corretta?
S->A
A->abAab
A->baAba
A->aAa
A->bAb
A->aba
A->Epsilon
Risposte
Manca qualcosa:
$A -> aAb$
$A -> bAa$
è quindi inutile avere le prime produzioni che hai messo. C'è inoltre un altro problema, sicuro che $A -> \epsilon$ sia necessaria?
$A -> aAb$
$A -> bAa$
è quindi inutile avere le prime produzioni che hai messo. C'è inoltre un altro problema, sicuro che $A -> \epsilon$ sia necessaria?
S->A
A->aAa
A->bAb
A->aba
Che ne dici?
Per verificare che sia giusta devo creare un albero o ci sono altri modi?
A->aAa
A->bAb
A->aba
Che ne dici?
Per verificare che sia giusta devo creare un albero o ci sono altri modi?
Dico che mancano ancora le produzioni che ho indicato prima. 
S->A
A->aAa
A->bAb
A→aAb
A→bAa
A->aba
Per verificare che sia giusta devo creare un albero o ci sono altri modi?
A->aAa
A->bAb
A→aAb
A→bAa
A->aba
Per verificare che sia giusta devo creare un albero o ci sono altri modi?
E' giusta, fidati.
Comunque puoi farlo con l'albero, certamente.
Comunque puoi farlo con l'albero, certamente.
non è per quello,è che non ho capito tanto bene come si costruiscono......
cmq esempio.... S->A poi S->aAa (regola 1) poi S->abAab (regola 2) poi S->aabAabb(regola 3) pero' se la regola 3 è corretta il linguaggio non è
a^n b^m aba a^n b^m
o sbaglio?
per definire un pda è consigliabile partire dalla grammatica o come per gli nfa si va ad "intuito"?
cmq esempio.... S->A poi S->aAa (regola 1) poi S->abAab (regola 2) poi S->aabAabb(regola 3) pero' se la regola 3 è corretta il linguaggio non è
a^n b^m aba a^n b^m
o sbaglio?
per definire un pda è consigliabile partire dalla grammatica o come per gli nfa si va ad "intuito"?
ragazzi consigli su come si costruiscono le grammatiche context free
Non c'è un algoritmo formale per generare grammatiche libere da contesto.
Personalmente trovo molto comodo formalizzare una espressione regolare quanto più vicina ad una stringa della grammatica, costruirne la relativa grammatica e poi estendere quest'ultima.
In alternativa avendo ben chiari i parser LL(1) e LR(1) puoi costruire una grammatica immaginando di ridurre sistematicamente una stringa "base" di essa scelta intelligentemente e poi applicare i dovuti aggiustamenti
Personalmente trovo molto comodo formalizzare una espressione regolare quanto più vicina ad una stringa della grammatica, costruirne la relativa grammatica e poi estendere quest'ultima.
In alternativa avendo ben chiari i parser LL(1) e LR(1) puoi costruire una grammatica immaginando di ridurre sistematicamente una stringa "base" di essa scelta intelligentemente e poi applicare i dovuti aggiustamenti
Ok se puoi mostrami un esempio....per i pda invece?
L'e.r. più simile alla grammatica proposta è:
$ (a|b)^*aba(a|b)^* $
Che è generata dalla grammatica:
$ S->ABA $
$ A->aA|bA|eps $
$ B->aba $
La grammatica che invece genera stringìhe palindrome di lunghezza dispari è:
$ S->aSa|bSb|a|b $
Siccome le nostre stringhe non devono essere per forza palindrome ma assicurare l'esistenza in posizione centrale di "aba" devo prendere la parte che genera:
$ (a|b)^* $
dalla prima grammatica e inserirla nella seconda, ottenendo:
$ S->aSb|aSa|bSa|bSb|a|b $
La parte che definisce il carattere "centrale" di questa grammatica è a|b, che quindi sostituisco con "aba".
$ S->aSb|aSa|bSa|bSb|aba $
Purtroppo questo è il metodo più formale possibile per creare grammatiche, non ne esiste uno sistematico, altrimenti sarebbe possibile far generare automaticamente grammatiche ad un calcolatore.
Basta pensare che le grammatiche sono specificate "a parole".
PDA, sta per?
$ (a|b)^*aba(a|b)^* $
Che è generata dalla grammatica:
$ S->ABA $
$ A->aA|bA|eps $
$ B->aba $
La grammatica che invece genera stringìhe palindrome di lunghezza dispari è:
$ S->aSa|bSb|a|b $
Siccome le nostre stringhe non devono essere per forza palindrome ma assicurare l'esistenza in posizione centrale di "aba" devo prendere la parte che genera:
$ (a|b)^* $
dalla prima grammatica e inserirla nella seconda, ottenendo:
$ S->aSb|aSa|bSa|bSb|a|b $
La parte che definisce il carattere "centrale" di questa grammatica è a|b, che quindi sostituisco con "aba".
$ S->aSb|aSa|bSa|bSb|aba $
Purtroppo questo è il metodo più formale possibile per creare grammatiche, non ne esiste uno sistematico, altrimenti sarebbe possibile far generare automaticamente grammatiche ad un calcolatore.
Basta pensare che le grammatiche sono specificate "a parole".
PDA, sta per?
Pda=automa a pila ...
Hai qualche esercizio da propormi per allenarmi nel costruire grammatiche contextfree?
Hai qualche esercizio da propormi per allenarmi nel costruire grammatiche contextfree?
a^n b ^[n+3] con n>0
La soluzione della prof e':
S->aSb | aT b
T->bb
La mia e'
S->aAbbbb
A->aAb|eps
Sono corrette?a me quella della prof non sembra
La soluzione della prof e':
S->aSb | aT b
T->bb
La mia e'
S->aAbbbb
A->aAb|eps
Sono corrette?a me quella della prof non sembra
"mictrt":
Pda=automa a pila ...
Hai qualche esercizio da propormi per allenarmi nel costruire grammatiche contextfree?
vedi qua, Eserciziario.
Io utilizzo le dispense dello stesso corso da cui provengono gli esercizi, sono molto ben fatti, perciò penso che anche gli esercizi lo siano
"mictrt":
a^n b ^[n+3] con n>0
La soluzione della prof e':
S->aSb | aT b
T->bb
La mia e'
S->aAbbbb
A->aAb|eps
Sono corrette?a me quella della prof non sembra
In quella della prof manca una b...
Anche la tua è corretta... solo che l'uso della epsilon è una bruttura, se riesci a non usarla è meglio, in questo caso quindi va evitata.
ok...mentre per gli automa a pila...suggerimenti?
datemi qualche consiglio per creare un automa a pila dalla grammatica corretta del primo post....
un aiutino?
Una domanda: quale testo usi? Ci dovrebbe essere spiegato come passare da una grammatica context-free a un PDA e viceversa.
In alternativa prova a dare un'occhiata qui, e poi magari ne riparliamo
http://www.cs.nuim.ie/~jpower/Courses/P ... index.html
[ Era già segnalato nella sezione dispense/appunti in rete, spero l'autore non lo rimuova ]
In alternativa prova a dare un'occhiata qui, e poi magari ne riparliamo
http://www.cs.nuim.ie/~jpower/Courses/P ... index.html
[ Era già segnalato nella sezione dispense/appunti in rete, spero l'autore non lo rimuova
]
grazie ma questo mi era sfuggito...ora ci provo
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo