九州大学 システム情報科学府 情報理工学専攻 2020年12月実施 オートマトンと言語

标签：

• 九州大学
• 确定性有限自动机
• 正则表达式
• 上下文无关文法

Author

祭音Myyura (co-authored with GPT 6 Astra)

Description

【問1】

状態数2の決定性有限オートマトンを考える。決定性有限オートマトン $M=(K,\Sigma,\delta,q_0,F)$ において、$K=\{q_0,q_1\}$、$\Sigma=\{a,b\}$、$F=\{q_0\}$ とする。ただし、$K,\Sigma,\delta,q_0,F$ はそれぞれ $M$ の状態集合、アルファベット、遷移関数、初期状態、最終状態の集合を表し、$a$ と $b$ は文字である。なお $\delta(p,x)=r$（$p,r\in K$、$x\in\Sigma$）は、$M$ が文字 $x$ を読むことで状態 $p$ から状態 $r$ に移ることを表す。$M$ によって受理される言語を $L(M)$ で表す。$\Sigma$ 上の正規表現 $e(a,b)$ が表す言語を、$\|e(a,b)\|$ で表す。次の各問いに答えよ。

(1) 図1は、$\delta(q_0,a)=q_0,\ \delta(q_0,b)=q_1$ である4種類の $\delta$ に対応する $M$ の状態遷移図である。図1の各 $M$ について $L(M)$ に含まれる文字列を説明せよ。

(2) $\delta(q_0,a)=\delta(q_0,b)=q_1$ のとき、可能な $M$ の状態遷移図を図1にならって全て与えよ。さらに、各 $M$ について $L(M)$ に含まれる文字列を説明せよ。

(3) 言語 $L=\|e(a,b)\|$ について、$\|e(b,a)\|$ を $L$ の交換言語と呼ぶ。たとえば、$L_0$ が文字 $a$ を偶数個含む文字列から構成される言語であるとき、$L_0$ の交換言語は文字 $b$ を偶数個含む文字列から構成される言語である。

　(1) と (2) とは異なる $\delta$ に対応する各 $M$ に対し、(1) あるいは (2) の言語の交換言語とならない $L(M)$ に含まれる文字列を説明せよ。

【問2】

文脈自由文法を4つ組 $(N,\Sigma,P,S)$ で表す。ただし、$N,\Sigma,P,S$ をそれぞれ非終端記号の集合、終端記号の集合、生成規則の集合、開始記号とする。$\Sigma$ 上の文字列 $w$ と終端記号 $x\in\Sigma$ に対して、$|w|_x$ を $w$ 中の $x$ の出現数とする。以下の各問に答えよ。

(A) 以下に示す言語 $L_i$（$i=1,2,3$）を導出する文脈自由文法 $(N_i,\Sigma_i,P_i,S)$ の生成規則の集合 $P_i$ を与えよ。

(1) $L_1=\{w\in\{a,b\}^*\mid |w|_a\ge3\}$。ただし $\Sigma_1=\{a,b\}$ である。答えには $N_1=\{S,X\}$ を用いよ。

(2) $L_2=\{w\in\{a,b\}^*\mid |w|_a\ge2|w|_b\}$。ただし $\Sigma_2=\{a,b\}$ である。答えには $N_2=\{S\}$ を用いよ。

(3) $L_3=\{a^ib^jc^k\mid i,j,k\ge0\text{ かつ }(2i=j\text{ または }3j=k)\}$。ただし $\Sigma_3=\{a,b,c\}$ である。答えには $N_3=\{S,V,X,Y,Z\}$ を用いよ。

(B) 以下に示す言語 $L_4,L_5$ は文脈自由言語であるか否か、証明せよ。

(4) $L_4=\varnothing$。

(5) 有限個の有限長文字列から構成される空でない任意の言語 $L_5$。

题目描述

【问1】

考虑一个具有两个状态的确定性有限自动机 $M=(K,\Sigma,\delta,q_0,F)$，其中 $K=\{q_0,q_1\}$、$\Sigma=\{a,b\}$、$F=\{q_0\}$。$K,\Sigma,\delta,q_0,F$ 分别表示状态集合、字母表、转移函数、初始状态和接受状态集合，$a,b$ 为字符。$\delta(p,x)=r$（$p,r\in K$、$x\in\Sigma$）表示自动机读入字符 $x$ 后从状态 $p$ 转移到状态 $r$。用 $L(M)$ 表示自动机接受的语言，用 $\|e(a,b)\|$ 表示字母表 $\Sigma$ 上的正则表达式 $e(a,b)$ 所表示的语言。回答下列问题。

(1) 上方图1给出了满足 $\delta(q_0,a)=q_0,\ \delta(q_0,b)=q_1$ 的全部四种转移函数对应的状态转移图。分别说明这些自动机接受的字符串。

(2) 当 $\delta(q_0,a)=\delta(q_0,b)=q_1$ 时，仿照图1，给出所有可能的状态转移图，并分别说明它们接受的字符串。

(3) 对于语言 $L=\|e(a,b)\|$，称 $\|e(b,a)\|$ 为 $L$ 的交换语言。例如，“包含偶数个 $a$ 的字符串”所组成的语言，其交换语言是“包含偶数个 $b$ 的字符串”所组成的语言。

对于转移函数不同于 (1)、(2) 的各个自动机，说明其中不属于 (1) 或 (2) 所得语言的交换语言的 $L(M)$ 包含哪些字符串。

【问2】

用四元组 $(N,\Sigma,P,S)$ 表示上下文无关文法，其中 $N,\Sigma,P,S$ 分别为非终结符集合、终结符集合、产生式集合和开始符号。对于 $\Sigma$ 上的字符串 $w$ 与终结符 $x\in\Sigma$，用 $|w|_x$ 表示 $x$ 在 $w$ 中出现的次数。回答下列问题。

(A)

给出生成下列语言 $L_i$（$i=1,2,3$）的上下文无关文法 $(N_i,\Sigma_i,P_i,S)$ 的产生式集合 $P_i$。

(1) $L_1=\{w\in\{a,b\}^*\mid |w|_a\ge3\}$。终结符集合为 $\Sigma_1=\{a,b\}$，必须使用非终结符集合 $N_1=\{S,X\}$。

(2) $L_2=\{w\in\{a,b\}^*\mid |w|_a\ge2|w|_b\}$。终结符集合为 $\Sigma_2=\{a,b\}$，必须使用非终结符集合 $N_2=\{S\}$。

(3) $L_3=\{a^ib^jc^k\mid i,j,k\ge0\text{ 且 }(2i=j\text{ 或 }3j=k)\}$。终结符集合为 $\Sigma_3=\{a,b,c\}$，必须使用非终结符集合 $N_3=\{S,V,X,Y,Z\}$。

(B)

证明下列语言是否为上下文无关语言。

(4) $L_4=\varnothing$。

(5) 任意非空语言 $L_5$，其中包含有限个有限长度的字符串。

Kai

【問1】

以下では $\varepsilon$ を空文字列、$+$ を正規表現の和とする。初期状態 $q_0$ が受理状態なので、どの $M$ も $\varepsilon$ を受理する。

(1)

図1を左から (i)、(ii)、(iii)、(iv) と呼ぶ。

図	$\delta(q_1,a)$	$\delta(q_1,b)$	受理する言語の正規表現
(i)	$q_1$	$q_1$	$a^*$
(ii)	$q_1$	$q_0$	$a^*(ba^*ba^*)^*$
(iii)	$q_0$	$q_1$	$\varepsilon+(a+b)^*a$
(iv)	$q_0$	$q_0$	$(a+b(a+b))^*$

• (i) $b$ を一度も含まない文字列である。$b$ を読むと $q_1$ に移り、その後は $q_0$ に戻れない。
• (ii) $b$ の出現数が偶数である文字列である。$a$ は状態を変えず、$b$ を読むたびに二つの状態を交互に移る。
• (iii) 空文字列、または末尾が $a$ である文字列である。どちらの状態からも、$a$ を読めば $q_0$、$b$ を読めば $q_1$ になる。
• (iv) ブロック $a$、$ba$、$bb$ の有限回の連結として表せる文字列である。$q_0$ では $a$ だけで1回の閉路となり、$b$ で $q_1$ へ移った場合は、その次の1文字が $a,b$ のどちらでも $q_0$ に戻る。したがって、左からこの規則で読み進めたとき、最後に未処理の $b$ が残らないことが受理条件となる。

(2)

$q_0$ からの二つの遷移が固定されているので、$\delta(q_1,a)$ と $\delta(q_1,b)$ の選び方は $2^2=4$ 通りである。全ての状態遷移図を以下に示す。二重丸が受理状態、外からの矢印が初期状態を示す。

図	$\delta(q_1,a)$	$\delta(q_1,b)$	受理する言語の正規表現
(i)	$q_1$	$q_1$	$\varepsilon$
(ii)	$q_0$	$q_1$	$((a+b)b^*a)^*$
(iii)	$q_1$	$q_0$	$((a+b)a^*b)^*$
(iv)	$q_0$	$q_0$	$((a+b)(a+b))^*$

• (i) 空文字列だけである。1文字でも読むと $q_1$ に移り、以後戻れない。言語は $\{\varepsilon\}$ であり、空言語 $\varnothing$ ではない。
• (ii) 「任意の1文字、続いて0個以上の $b$、最後に $a$」というブロックを0回以上連結した文字列である。各ブロックが $q_0$ から出て初めて $q_0$ に戻る経路に対応する。
• (iii) 「任意の1文字、続いて0個以上の $a$、最後に $b$」というブロックを0回以上連結した文字列である。
• (iv) 長さが偶数である文字列である。文字の種類によらず、1文字読むたびに状態が切り替わる。

(3)

遷移関数は全体で $2^4=16$ 通りある。(1)、(2) で扱っていないものは、$q_0$ からの遷移によって次の二つに分かれる。

$\delta(q_0,a)=q_1,\ \delta(q_0,b)=q_0$ の場合： $a,b$ を交換すると (1) の場合になる。$q_1$ からの遷移も同時に交換されるため、この場合の全4通りの受理言語は (1) のいずれかの交換言語であり、求める対象ではない。

$\delta(q_0,a)=\delta(q_0,b)=q_0$ の場合： どの文字を読んでも $q_0$ にとどまるため、$q_1$ は到達不能である。したがって、$\delta(q_1,a),\delta(q_1,b)$ の選び方4通りの全てについて、

$$\boxed{L(M)=\Sigma^*=\{a,b\}^*=\|(a+b)^*\|}.$$

すなわち、空文字列を含む $a,b$ 上の全ての文字列を受理する。(1) では $b$、(2) では $a$ のように、各場合に少なくとも一つ不受理の文字列がある。文字の交換は全単射なので、それらの交換言語も $\Sigma^*$ にはならない。よって上記が求める言語であり、該当する遷移関数は4通りある。状態集合は指定どおり $\{q_0,q_1\}$ のままでよい。

【問2】

(A)(1)

次の生成規則を与える。

$$\boxed{\begin{aligned} S&\to XaXaXaX,\\ X&\to aX\mid bX\mid\varepsilon. \end{aligned}}$$

$X$ は $\{a,b\}^*$ の任意の文字列を生成する。$S$ の規則には3個の $a$ が明示されているので、生成される文字列の $a$ は3個以上となる。逆に、$a$ を3個以上含む文字列から3個の $a$ を選ぶと、その前後と間を四つの $X$ で生成できる。よって生成言語はちょうど $L_1$ である。

(A)(2)

非終端記号を $S$ だけとして、次の生成規則を与える。

$$\boxed{\begin{aligned} S\to{}&SaS\\ \mid{}&SaSaSbS\\ \mid{}&SaSbSaS\\ \mid{}&SbSaSaS\\ \mid{}&\varepsilon. \end{aligned}}$$

生成される文字列が条件を満たすこと。 $d(w)=|w|_a-2|w|_b$ と置く。$SaS$ は $d$ を1増やし、他の三つの非空規則は $a$ を2個、$b$ を1個加えるので $d$ を変えない。$S\to\varepsilon$ の値は0である。導出木について帰納すれば、生成される全ての文字列で $d(w)\ge0$ となる。

条件を満たす全ての文字列を生成できること。 $d(w)\ge0$ で $b$ を含む文字列は、連続部分文字列 $aab,aba,baa$ のいずれかを含む。実際、これらを全て含まないと仮定すると、$a$ は連続できず、二つの $a$ の間には少なくとも2個の $b$ が必要になる。$A=|w|_a,B=|w|_b$ とすると、$B\ge1$ および $A\ge2B$ から $A\ge2$ である一方、

$$B\ge2(A-1),\qquad A\ge2B \quad\Longrightarrow\quad 3A\le4$$

となり矛盾する。

そこで $aab,aba,baa$ のいずれかを削除する。この操作は $d(w)$ を変えず、$b$ を1個減らすので、繰り返すと $a$ だけの文字列になる。その $a$ も1個ずつ削除して空文字列にできる。

これを逆にたどれば、空文字列から任意の位置へ $a$、$aab$、$aba$、$baa$ を挿入して元の文字列を復元できる。上の文法では、挿入した文字の前後と各文字間に $S$ を残せるため、これら全ての挿入を実現できる。最後に残った $S$ を $\varepsilon$ にすればよい。よって生成言語はちょうど $L_2$ である。特に $aa$ も $S\Rightarrow SaS\Rightarrow SaSaS\Rightarrow aa$ と生成できる。

(A)(3)

条件の「または」に従って二つの言語の和に分ける。

$$\begin{aligned} L_3={}&\{a^ib^{2i}c^k\mid i,k\ge0\}\\ &\cup\{a^ib^jc^{3j}\mid i,j\ge0\}. \end{aligned}$$

指定された $N_3=\{S,V,X,Y,Z\}$ を用いて、

$$\boxed{\begin{aligned} S&\to VZ\mid XY,\\ V&\to aVbb\mid\varepsilon,\\ Z&\to cZ\mid\varepsilon,\\ X&\to aX\mid\varepsilon,\\ Y&\to bYccc\mid\varepsilon \end{aligned}}$$

とする。$V$ は $a^ib^{2i}$、$Z$ は任意の $c^k$ を生成するので、$VZ$ は第1の言語を生成する。$X$ は任意の $a^i$、$Y$ は $b^jc^{3j}$ を生成するので、$XY$ は第2の言語を生成する。いずれも文字の順序 $a^*b^*c^*$ が保たれ、$i,j,k=0$ の場合も含まれる。したがって生成言語は $L_3$ と一致する。

(B)(4)

$L_4=\varnothing$ は文脈自由言語である。 例えば、

$$G_4=(\{S\},\{a\},\{S\to S\},S)$$

という文脈自由文法を考える。$S$ からの導出では常に非終端記号 $S$ が残り、終端記号だけからなる文字列は一つも得られない。したがって $L(G_4)=\varnothing$ である。$\varepsilon$ も生成されないので、$\varnothing$ と $\{\varepsilon\}$ を混同していない。

(B)(5)

任意の有限言語 $L_5$ は文脈自由言語である。 $L_5=\{w_1,\ldots,w_m\}$（$m\ge1$）と書き、その終端記号の集合を $\Sigma$ とする。生成規則を

$$P_5=\{S\to w_i\mid1\le i\le m\}$$

とすれば、文法 $(\{S\},\Sigma,P_5,S)$ が生成する文字列はちょうど $w_1,\ldots,w_m$ である。$w_i=\varepsilon$ なら $S\to\varepsilon$ を含めればよい。生成規則は有限個で、各右辺も有限長であるため、有効な文脈自由文法となる。なお、有限言語は正規言語でもある。

Reference

• 九州大学大学院システム情報科学府 情報理工学専攻：令和3年度入学試験問題、2020年12月5日実施、専門科目 C「オートマトンと言語」、【問1】【問2】。
• 九州大学：修士課程入試・過去問題案内