最小文法問題

データ圧縮と形式文法理論において、最小文法問題（さいしょうぶんぽうもんだい、英語: smallest grammar problem）は、与えられた文字列を生成する最小の文脈自由文法を見つける問題である。文法のサイズは、生成規則の右側のシンボルの数として定義するとしている者^[1]や、それに規則の数を加えるとする者^[2]もいる。この問題（の決定版）はNP完全である^[1]。