NCEで書けた！！希ｶﾞｽ・・・
Σ = 大文字と小文字のやつ。Δ = 小文字のやつ。
P = {π : π ⊆ V[X] × (2^Σ)}で書いてみた。

M := s-G , (s, {}), (G, {})
C := C-D , (C, {s, g, c, d, G, C, D}), (D, {})
C := c　　 , (c, {s, g, c, d, G, C, D})
G := C-G , (C, {s, C}), (G, {})
G := g　　 , (g, {s, C})
D := C-D , (C, {c, C}), (D, {})
D := d　　 , (d, {c, C})

Cは後々cにする非終端ラベルで、任意個数のDをにょきっと出せる。
Gは後々gにする非終端ラベルで、G自身が末端になるように正解ルート上にCを伸ばしていく。
Dは後々dにする非終端ラベルで、D自身が末端になるように正解ルート以外の全域にCを伸ばしていく。