R05-C-問2

問2

文脈自由文法を４つ組 $(N,\Sigma ,P,S)$ で表す。ただし、$N$、$\Sigma$、$P$、$S$ をそれぞれ非終端記号の集合、終端記号の集合、生成規則の集合、開始記号とする。$\Sigma =\{a,b\}$ とする。
(1) $L_1=\{a^i{b}^j|0\le 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\le i<j\}\cup \{a^i{b}^j|i>j\ge 0\}={\Sigma }^{\ast }\setminus \{a^i{b}^i|i\ge 0\}$
• $L_2\cap \{a^i{b}^j|0\le i<j\}=L_2\cap \{a^i{b}^j|i>j\ge 0\}=\varnothing$
  言語 $L_2$ を生成する文脈自由文法 $G_2=(N_2,\Sigma ,P_2,S)$ の生成規則の集合 $P_2$ を与えよ。ただし $|N_2|\le 2$ とする。
  (3) $L_3={\Sigma }^{\ast }\setminus \{a^i{b}^i|i\ge 0\}$ とする。以下のような生成規則の集合を持ち、かつ言語 $L_3$ を生成する文脈自由文法 $G_3=(N_3,\Sigma ,P_3,S)$ を考える。ただし $N_3=\{S,X\}$ であり、$ϵ$ は空文字列を表す。(i), (ii), (iii) を与えよ。
  $S\to \boxed{(i)}|\boxed{(ii)}|\boxed{(iii)}$
  $X\to bX|aX|ϵ$
  (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 }^{\ast }\setminus L(M)$ とする。言語 $L_4$ を生成する文脈自由文法 $G_4=(N_4,\Sigma ,P_4,S)$ の生成規則の集合 $P_4$ を与えよ。ただし $|N_4|\le 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\le 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\le i<j\}\cup \{a^i{b}^j|i>j\ge 0\}={\Sigma }^{\ast }\setminus \{a^i{b}^i|i\ge 0\}$
• $L_2\cap \{a^i{b}^j|0\le i<j\}=L_2\cap \{a^i{b}^j|i>j\ge 0\}=\varnothing$
  给出生成语言 $L_2$ 的上下文无关文法 $G_2=(N_2,\Sigma ,P_2,S)$ 的生成规则集合 $P_2$，其中 $|N_2|\le 2$。
  (3) 设 $L_3={\Sigma }^{\ast }\setminus \{a^i{b}^i|i\ge 0\}$。考虑以下形式的生成规则集合，并生成语言 $L_3$ 的上下文无关文法 $G_3=(N_3,\Sigma ,P_3,S)$，其中 $N_3=\{S,X\}$，$ϵ$ 表示空字符串。给出 (i), (ii), (iii)。

$$\begin{gathered} S\to (i)|(ii)|(iii) \\ X\to bX|aX|ϵ \end{gathered}$$

(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 }^{\ast }\setminus L(M)$。给出生成语言 $L_4$ 的上下文无关文法 $G_4=(N_4,\Sigma ,P_4,S)$ 的生成规则集合 $P_4$，其中 $|N_4|\le 2$。

解答

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

$$S\to aSb|Sb|b$$

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

$$\begin{gathered} S\to aSb|aX \\ X\to bX|ϵ \end{gathered}$$

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

$$\begin{gathered} S\to aSb|aX|bX \\ X\to aX|bX|ϵ \end{gathered}$$

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

$$\begin{gathered} S\to aSb|aX|bX \\ X\to aX|bX|ϵ \end{gathered}$$

---

DeepSeekV3

(1) Grammar for $L_1=\{a^i{b}^j\mid 0\le 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\ge 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 }^{\ast }\setminus \{a^i{b}^i\mid i\ge 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 ϵ$$

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

(4) Grammar for $L_4={\Sigma }^{\ast }\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$.