問2

文脈自由文法を４つ組 $(N, \Sigma, P, S)$ で表す。ただし、$N$、$\Sigma$、$P$、$S$ をそれぞれ非終端記号の集合、終端記号の集合、生成規則の集合、開始記号とする。$\Sigma = \{a, b\}$ とする。 (1) $L_1 = \{a^i b^j | 0 \leq i < j\}$ とする。言語 $L_1$ を生成する文脈自由文法 $G_1 = (N_1, \Sigma, P_1, S)$ の生成規則の集合 $P_1$ を与えよ。ただし $|N_1| = 1$ とする。 (2) $L_2$ を以下の条件を満たす言語とする。

• $L_2 \cup \{a^i b^j | 0 \leq i < j\} \cup \{a^i b^j | i > j \geq 0\} = \Sigma^* \setminus \{a^i b^i | i \geq 0\}$
• $L_2 \cap \{a^i b^j | 0 \leq i < j\} = L_2 \cap \{a^i b^j | i > j \geq 0\} = \emptyset$ 言語 $L_2$ を生成する文脈自由文法 $G_2 = (N_2, \Sigma, P_2, S)$ の生成規則の集合 $P_2$ を与えよ。ただし $|N_2| \leq 2$ とする。 (3) $L_3 = \Sigma^* \setminus \{a^i b^i | i \geq 0\}$ とする。以下のような生成規則の集合を持ち、かつ言語 $L_3$ を生成する文脈自由文法 $G_3 = (N_3, \Sigma, P_3, S)$ を考える。ただし $N_3 = \{S, X\}$ であり、$\epsilon$ は空文字列を表す。(i), (ii), (iii) を与えよ。

$$S \rightarrow \boxed{(i)} | \boxed{(ii)} | \boxed{(iii)}$$

$$X \rightarrow bX | aX | \epsilon$$

(4) 以下の状態遷移図を持つ決定性有限オートマトン $M = (K, \Sigma, \delta, q_0, F)$ で受理される言語を $L(M)$ とする。ただし、$K = \{q_0, q_1, q_2\}$、$\Sigma$、$\delta$、$q_0$、$F = \{q_0\}$ は、それぞれ $M$ の状態の集合、アルファベット、遷移関数、初期状態、受理状態の集合を表す。$L_4 = \Sigma^* \setminus L(M)$ とする。言語 $L_4$ を生成する文脈自由文法 $G_4 = (N_4, \Sigma, P_4, S)$ の生成規則の集合 $P_4$ を与えよ。ただし $|N_4| \leq 2$ とする。

\usepackage{tikz}
\begin{document}
\begin{tikzpicture}[->, shorten >=1pt, auto, semithick]
  % Define states with absolute positions
  \node[double,circle, draw] (q0) at (0, 0) {$q_0$};
  \node[circle, draw] (q1) at (2, 0) {$q_1$}; % sqrt(3)*2 = 3.46 for equilateral triangle
  \node[circle, draw] (q2) at (1, -1.732) {$q_2$};
  % Transitions
  \path (q0) edge[bend left] node[midway] {a} (q1)
        (q0) edge node[below] {b} (q2)
        (q1) edge node[below] {b} (q0)
        (q1) edge node[midway] {a} (q2)
        (q2) edge[loop right] node {a, b} ();
\end{tikzpicture}
\end{document}

中文翻译

上下文无关文法用四元组 $(N, \Sigma, P, S)$ 表示，其中 $N$、$\Sigma$、$P$、$S$ 分别表示非终结符集合、终结符集合、生成规则集合和开始符号。设 $\Sigma = \{a, b\}$。 (1) 设 $L_1 = \{a^i b^j | 0 \leq i < j\}$。给出生成语言 $L_1$ 的上下文无关文法 $G_1 = (N_1, \Sigma, P_1, S)$ 的生成规则集合 $P_1$，其中 $|N_1| = 1$。 (2) 设 $L_2$ 为满足以下条件的语言：

• $L_2 \cup \{a^i b^j | 0 \leq i < j\} \cup \{a^i b^j | i > j \geq 0\} = \Sigma^* \setminus \{a^i b^i | i \geq 0\}$
• $L_2 \cap \{a^i b^j | 0 \leq i < j\} = L_2 \cap \{a^i b^j | i > j \geq 0\} = \emptyset$ 给出生成语言 $L_2$ 的上下文无关文法 $G_2 = (N_2, \Sigma, P_2, S)$ 的生成规则集合 $P_2$，其中 $|N_2| \leq 2$。 (3) 设 $L_3 = \Sigma^* \setminus \{a^i b^i | i \geq 0\}$。考虑以下形式的生成规则集合，并生成语言 $L_3$ 的上下文无关文法 $G_3 = (N_3, \Sigma, P_3, S)$，其中 $N_3 = \{S, X\}$，$\epsilon$ 表示空字符串。给出 (i), (ii), (iii)。

$$S \rightarrow (i) | (ii) | (iii) \\ X \rightarrow bX | aX | \epsilon$$

(4) 设 $M = (K, \Sigma, \delta, q_0, F)$ 是一个确定性有限自动机，其状态转移图如下，其中 $K = \{q_0, q_1, q_2\}$、$\Sigma$、$\delta$、$q_0$、$F = \{q_0\}$ 分别表示 $M$ 的状态集合、字母表、转移函数、初始状态和接受状态集合。设 $L_4 = \Sigma^* \setminus L(M)$。给出生成语言 $L_4$ 的上下文无关文法 $G_4 = (N_4, \Sigma, P_4, S)$ 的生成规则集合 $P_4$，其中 $|N_4| \leq 2$。

解答

(1) 生成规则集合 $P_1$ 为：

$$S \rightarrow aSb | Sb | b$$

(2) 生成规则集合 $P_2$ 为：

$$S \rightarrow aSb | aX \\ X \rightarrow bX | \epsilon$$

(3) 生成规则集合 $P_3$ 为：

$$S \rightarrow aSb | aX | bX \\ X \rightarrow aX | bX | \epsilon$$

(4) 生成规则集合 $P_4$ 为：

$$S \rightarrow aSb | aX | bX \\ X \rightarrow aX | bX | \epsilon$$

---

DeepSeekV3

(1) Grammar for $L_1 = \{a^i b^j \mid 0 \leq i < j\}$

We need a grammar where the number of $a$'s is less than the number of $b$'s.

• Non-terminals: $N_1 = \{S\}$
• Terminals: $\Sigma = \{a, b\}$
• Start symbol: $S$
• Production rules:

  $$P_1 = \{ S \to aSb \mid b \}$$

This grammar generates strings where for each $a$, there is at least one additional $b$, ensuring $i < j$.

(2) Grammar for $L_2$

$L_2$ consists of all strings not of the form $a^i b^j$ (where $i, j \geq 0$), i.e., strings with mixed $a$'s and $b$'s.

• Non-terminals: $N_2 = \{S, A\}$
• Terminals: $\Sigma = \{a, b\}$
• Start symbol: $S$
• Production rules:

  $$P_2 = \{ S \to bS \mid aA, \ A \to aA \mid bA \mid a \mid b \}$$

This grammar generates strings where $b$'s can appear before $a$'s, ensuring they are not in the form $a^i b^j$.

(3) Grammar for $L_3 = \Sigma^* \setminus \{a^i b^i \mid i \geq 0\}$

We need to generate all strings except those where the number of $a$'s equals the number of $b$'s.

• Non-terminals: $N_3 = \{S, X\}$
• Terminals: $\Sigma = \{a, b\}$
• Start symbol: $S$
• Production rules:

  $$S \to aS \mid bS \mid aX \mid bX$$

  $$X \to aX \mid bX \mid \epsilon$$

This grammar generates all strings with unequal numbers of $a$'s and $b$'s.

(4) Grammar for $L_4 = \Sigma^* \setminus L(M)$

The DFA $M$ accepts strings with an odd number of $a$'s ending in $b$. $L_4$ is the complement of this language.

• Non-terminals: $N_4 = \{S, X\}$
• Terminals: $\Sigma = \{a, b\}$
• Start symbol: $S$
• Production rules:

  $$S \to aX \mid bX$$

  $$X \to aX \mid bX \mid a \mid b$$

This grammar generates strings that either have an even number of $a$'s or do not end in $b$.