Esercizio svolto linguaggio libero da contesto
Esercizio svolto linguaggio libero da contesto
Dato il linguaggio L, stabilire se è libero:
L = {w ∈ {0,1,2} | #0(w) + #1(w) = #2(w)}
Per svolgere questo esercizio, dobbiamo semplicemente trovare una grammatica G che genera questo linguaggio. Quindi:
G = (X,V,S,P) X = {0,1,2} V = {S,A,B}
P = {
S -> ε | A | B
A -> S0S2S | S2S0S
B -> S1S2S | S2S1S
}
Il linguaggio è libero da contesto perché generata da una grammatica libera da contesto.