京都大学 情報学研究科 知能情報学専攻 2019年2月実施 専門科目 F1-2

标签：

• Kyoto-University
• Context-Free-Grammar

Author

祭音Myyura (co-authored with GPT 5.2 extended thinking)

Description

Give context-free grammars that generate the following languages. In all parts, the alphabet (terminal character set) is $\{0, 1\}$.

Q.1 $\{ w \mid w \text{ contains at least three 1s} \}$

Q.2 $\{ w \mid \text{the length of } w \text{ is odd and its middle symbol is a } 0 \}$

Q.3 $\{ w \mid w = w^R, \text{ where } \mathcal{R} \text{ denotes writing backwards, that is, } w \text{ is a palindrome} \}$

题目描述

对下列每种语言分别给出一个上下文无关文法；所有问题的终结符字母表均为 $\{0,1\}$。

1. $\{w\mid w\text{ 至少含三个 }1\}$；
2. $\{w\mid |w|\text{ 为奇数且正中间符号为 }0\}$；
3. $\{w\mid w=w^R\}$，其中 $w^R$ 表示逆序书写 $w$，即该语言为所有二进制回文串。

考点

• 上下文无关文法构造：分别用非终结符记录至少三个指定符号、围绕中心同步生成两侧字符，以及递归生成回文结构。

Kai

Q.1

• Terminals: $\Sigma={0,1}$
• Nonterminals: $\{S,A\}$
• Start symbol: $S$
• Productions:

$$\begin{aligned} S &\to A \ 1 \ A \ 1 \ A \ 1 \ A \\ A &\to 0A \mid 1A \mid \varepsilon \end{aligned}$$

Here $A$ generates any binary string, i.e. $L(A)=\Sigma^*$.

Q.2

A string has odd length and middle symbol $0$ iff it can be written as

$$w = x\ 0\ y \quad\text{with } |x|=|y|.$$

Grammar (G_2)

• Terminals: $\Sigma=\{0,1\}$
• Nonterminals: $\{S\}$
• Start symbol: $S$
• Productions:

$$S \to 0 \mid 0S0 \mid 0S1 \mid 1S0 \mid 1S1$$

Intuition: Start with the center $0$. Each step adds one symbol on the left and one on the right, preserving odd length and keeping the center fixed.

Q.3

• Terminals: $\Sigma=\{0,1\}$
• Nonterminals: $\{S\}$
• Start symbol: $S$
• Productions:

$$S \to \varepsilon \mid 0 \mid 1 \mid 0S0 \mid 1S1$$