Esercizio svolto: grammatica dipendete da contesto 1
Esercizio svolto: grammatica dipendete da contesto
Dato il linguaggio L ricavare una grammatica L(G) = L.
L = {an (ab)n an | n > 0}
Iniziamo a studiare questo linguaggio:
L = { aaba, aaababaa, aaaabababaaa, …. }
G = (X, V, S, P) X = {a,b} V = {S,A,B,C}
P = {
S -> ABC | ASBC
A -> a
B -> ab
C -> a
CB -> BC
}
Grammatica dipendente da contesto (tipo 1)
Ciao, scusatemi avrei un dubbio: la produzione CB -> BC non è una produzione contestuale ma monotona. Quindi la grammatica non dovrebbe essere monotona? Grazie.
ciao, si giusto! La produzione CB -> BC è monotona ma non contestuale. Per renderla contestuale bisogna aggiungere le produzioni:
CB → XB
XB → XC
XC → BC