京都大学情報学研究科知能情報学専攻 2025年8月実施専門科目 S-5

Author

文法を考える。ここで、はそれぞれ終端記号の有限集合、非終端記号の有限集合、生成規則の有限集合、開始記号である。は空文字列を表す。以下の設問ではとする。

設問 1　言語をすべての回文からなる集合とする。回文とは前向きに読んだ場合と後ろ向きに読んだ場合とで同じになる文字列である。はを含むとする。を生成する文脈自由文法のを示せ。ただしとする。

設問 2　とする文脈自由文法について、が生成するどの文字列も部分列としてを含まないことを証明せよ。

設問 3　言語をの数がの数よりも多いすべての文字列の集合とする。 (1) を生成する文脈自由文法のとを示せ。 (2) その文法の健全性（この文法が生成する文字列はすべてに含まれること）を証明せよ。 (3) その文法の完全性（に含まれる文字列はすべてこの文法が生成できること）を証明せよ。

設問 4　の補集合が文脈自由言語であることを証明せよ。