Esercizio grammatica linguaggi di programmazione
Esercizio svolto: grammatica
Dato il linguaggio
L = {0n 1m 0k | k > n+m > 0}
definire la grammatica.
G = (X,V,S,P)
X = (0,1)
V = (S,A,B,C,D)
P = {
S -> 100 | 000 | 0A00D
A -> 0A0 | B
B -> 1C0
C -> 1C0 | ϵ
D -> 0D | ϵ
}
Grammatica libera da contesto (tipo 2)
Potrei anche usare questa grammatica?
S -> MK0
M -> 0M0 | N | ϵ
N -> 1N0 | ϵ
K -> K0 | ϵ
Sì, la grammatica che hai proposto è corretta.
Un’altra possibile grammatica per il linguaggio L è questa:
S -> 0S0 | A
A -> 0A1B | ε
B -> 0B | ε