Linguaggi di programmazione: esercizio 3 grammatica

Dato il linguaggio

 

L = {w € {a,b,c}* | |w| = 3*n_a(w) }

 

trovare la grammatica.

 

Vediamo quali stringhe può generare il linguaggio:

L = {abc, acb, bac, cab, bca, cba, aabbcc, ……}

 

G = (X,V,S,P)

X = (a,b,c)

V = (S,B,C)

 

P = {

S => λ | aBCS | aBC | BCaS | BCa | BaCS | BaC | aCBS | aCB | CaBS | CaB | CBaS | CBa

B => b

C => c

}

 

oppure

 

P = {

S => λ | SaSBSB | SBSaSB | SBSBSa

B => b | c

}

 

Entrambe le grammatiche sono context-free (tipo 2)