Linguaggi di programmazione: esercizio 18 grammatica

Esercizio svolto: grammatica

Dato il linguaggio

L = {0ⁿ 1^m | n ≥ 0, 0 ≤ m ≤ 2n}

definire la grammatica.

Studiamo questo linguaggio trovando le varie stringhe minime:
L = { ϵ, 0, 01, 011, 00, 001, 0011, 00111, 001111, …. }

G = (X,V,S,P)

X = (0,1)

V = (S,B)

P = {
S -> ϵ | 0S | 0SB
B -> 1 | 11
}

Grammatica libera da contesto (tipo 2)

Oppure:

V = (S)

P = {
S -> ϵ | 0S | 0S1 | 0S11
}

Grammatica libera da contesto (tipo 2)