Esercizio svolto: grammatica dipendete da contesto

Esercizio svolto: grammatica dipendete da contesto

Dato il linguaggio L ricavare una grammatica L(G) = L.

L = {aⁿ b^m c^k | n ≤ m ≤ k}

Iniziamo a studiare questo linguaggio:

L = { ε, c, bc, abc, abbcc, aaabbbccc …. }

G = (X, V, S, P)      X = {a,b,c}      V = {S,B,C,D,E}

P = {
S -> aSBC | D
D -> BDC | E
EC -> CE
EB -> BE
CB -> BC
aB -> ab
bB -> bb
bC -> bc
cC -> cc
E -> ε | cE
}

Grammatica dipendente da contesto (tipo 1)