京都大学 情報学研究科 知能情報学専攻 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\}$ の補集合が文脈自由言語であることを証明せよ。

题目描述

考虑文法 $G=(\Sigma,N,P,S)$，其中 $\Sigma$、$N$、$P$、$S$ 分别表示有限终结符集、有限非终结符集、有限产生式集和开始符号，$\epsilon$ 表示空串。以下各题均令 $\Sigma=\{a,b\}$。

1. 令语言 $L$ 为所有回文组成的集合。回文是正向读取与反向读取完全相同的字符串，并规定 $\epsilon\in L$。在 $N=\{S\}$ 的条件下，给出生成 $L$ 的上下文无关文法的产生式集 $P$。

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^nb^n\mid n\geq0\}$$

   的补集是上下文无关语言。