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

标签：

• Kyushu-University
• Nondeterministic-Finite-Automaton
• Regular-Expression
• Deterministic-Finite-Automaton-Minimization
• Context-Free-Grammar
• Context-Free-Language-Closure-Properties

Author

Zero

Description

【問１】

以下の遷移図を持つ非決定性有限オートマトン $M = (K,\Sigma,\delta,q_0,F)$ に対し, 次の各問いに答えよ。ただし, $K = \{q_0,q_1,q_2,q_3,q_4\}$, $\Sigma = \{a,b\}$, $\delta$, $q_0$, $F = \{q_1,q_2,q_4\}$ は, それぞれ状態の集合, アルファベット, 遷移関数, 初期状態, 最終状態の集合を表す。$M$ によって受理される言語を $L$ とする。

(1) $L$ に含まれる長さ $4$ の文字列をすべて列挙せよ。

(2) $L$ に含まれる任意の文字列を, 正規表現 $(\alpha + \beta)(\alpha + \beta)^*$ を用いて表すことができる。ただし, $\alpha$ と $\beta$ はともに $\Sigma$ 上の文字列である。これらの文字列 $\alpha$ と $\beta$ を与えよ。

(3) $w$ を $\Sigma$ 上の文字列とする。以下の $2$ つの命題はそれぞれ真であるか偽であるか。真ならば理由を説明し, 偽ならば反例を与えよ。

• (a) 「 $w \in L$ ならば, $bb$ は $w$ の部分文字列ではない。」

• (b) 「 $bb$ が $w$ の部分文字列でないならば, $w \in L$ である。」

(4) $L$ を受理する状態数最小の決定性有限オートマトンの遷移図を与えよ。

【問２】

文脈自由文法 $G_1 = (N, \Sigma, P_1, S)$, $G_2 = (N, \Sigma, P_2, S)$ を考える． ただし，$N = \{S, A, B\}$, $\Sigma = \{a, b, c\}$, $P_i \ (i = 1, 2)$, $S$ はそれぞれ非終端記号の集合，終端記号の集合，生成規則の集合，開始記号とする. ここで, $P_1 = \{S \to AB, A \to ab \mid aAb, B \to c \mid Bc\}$, $P_2 = \{S \to AB, A \to a \mid aA, B \to bBc \mid bc\}$ とする．

(1) $G_1$ による文字列 $aabbc$ の導出過程を与えよ．

(2) $G_1$ が生成する言語 $L(G_1)$ に含まれる文字列を説明せよ．

(3) $G_2$ が生成する言語 $L(G_2)$ に含まれる文字列を説明せよ．

(4) 言語 $L(G_1) \cup L(G_2)$ を生成する文脈自由文法 $G_3 = (N_3, \Sigma, P_3, S)$ の生成規則の集合 $P_3$ を与えよ．ただし, $N_3 = \{S, A, B, C, D\}$.

Kai

【問１】

(1)

$b$ で終わることがない、かつ $b$ を連続で含まないことが条件になっているので

$$aaaa,aaba,abaa,baaa,baba$$

(2)

(1) を基に考えると

$$\alpha = a,\beta = ba$$

(3)

(a)

真;

理由：(2) より $\Sigma$ 上の文字列 $w$ は, $(a + ba)(a + ba)^*$ と表せるので、$b$ の後に連続して $b$ がくることがないから。

(b)

偽;

反例：$ab$

(4)

		a	b
$\rightarrow$	$q_0$	$q_1$	$q_3$
$*$	$q_1$	$q_1$	$q_3$
$*$	$q_2$	$q_1$	$q_3$
	$q_3$	$\{q_1,q_4\}$	$\emptyset$
$*$	$q_4$	$q_1$	$q_3$
	$\emptyset$	$\emptyset$	$\emptyset$

上の表から $q_1,q_2,\{q_1,q_4\}$ が等しいことがわかる。また、$q_4$ はどの状態からも遷移先になっていないことが。

よって、遷移表は以下のようになる。

		a	b
$\rightarrow$	$q_0$	$q_1$	$q_3$
$*$	$q_1$	$q_1$	$q_3$
	$q_3$	$q_1$	$\emptyset$
	$\emptyset$	$\emptyset$	$\emptyset$

ゆえに、求める状態数最小の決定性有限オートマトン $a$ 遷移図は

【問２】

(1)

$$S \to AB \to aAbc \to aabbc$$

(2)

$$L(G_1) = \{a^n b^n c^m \mid n \geq 1, m \geq 1\}$$

(3)

$$L(G_2) = \{a^m b^n c^n \mid m \geq 1, n \geq 1\}$$

(4)

$$\begin{aligned} P_3 = \{&S \to AB \mid CD \\ &A \to ab \mid aAb \\ &B \to c \mid Bc \\ &C \to a \mid aC \\ &D \to bDc \mid bc \} \end{aligned}$$