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

标签：

• Kyoto-University
• Context-Free-Grammar
• Context-Free-Language-Closure-Properties

Author

itsuitsuki

Description

文法 $G = (\Sigma, N, P, S)$ を考える。ここで、 $\Sigma, N, P, S$ はそれぞれ終端記号の有限集合、非終端記号の有限集合、生成規則の有限集合、開始記号である。 $\epsilon$ は空文字列を表す。 以下の設問では $\Sigma = \{a, b\}$ とする。

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

設問 2　$N = \{S\}, P = \{S \to aS \mid Sb \mid a \mid b\}$ とする文脈自由文法 $G$ について、 $G$ が生成するどの文字列も部分列として $ba$ を含まないことを証明せよ。

設問 3　言語 $L$ を $a$ の数が $b$ の数よりも多いすべての文字列の集合とする。

1. $L$ を生成する文脈自由文法の $N$ と $P$ を示せ。
2. その文法の健全性（この文法が生成する文字列はすべて $L$ に含まれること）を証明せよ。
3. その文法の完全性（$L$ に含まれる文字列はすべてこの文法が生成できること）を証明せよ。

設問 4　$L = \{a^n b^n | n \geq 0\}$ の補集合が文脈自由言語であることを証明せよ。