データ圧縮と形式文法理論において、最小文法問題（さいしょうぶんぽうもんだい、）は、与えられた文字列を生成する最小の文脈自由文法を見つける問題である。文法のサイズは、生成規則の右側のシンボルの数として定義するとしている者や、それに規則の数を加えるとする者Florian Benz and Timo Kötzing, “An effective heuristic for the smallest grammar problem,” Proceeding of the fifteenth annual conference on Genetic and evolutionary computation conference - GECCO ’13, 2013. もいる。この問題（の決定版）はNP完全である。
関連項目 文法圧縮 コルモゴロフ複雑性 可逆圧縮
脚注