Linguaggi di programmazione: esercizio 16 grammatica
Esercizio svolto: grammatica libera da contesto
Dato il linguaggio
L = {w ∈ {a,b}* w ha un numero di ‘b’ doppio rispetto a quello di ‘a’}
definire la grammatica.
Iniziamo a studiare questo linguaggio:
L = { ϵ, abb, aabbbb, bab, bba, babbab, abbbab, … }
G = (X,V,S,P)
X = (a,b)
V = (S,B)
P = {
S -> ϵ | aSbb | abbS | abSb | bB
B -> aSb | bSa | baS | Sab
}
Grammatica libera da contesto (tipo 2)