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

标签：

• Kyushu-University
• Nondeterministic-Finite-Automaton
• Deterministic-Finite-Automaton-Minimization
• Product-Automaton
• Context-Free-Grammar
• Parse-Tree

Author

Zero, 祭音Myyura

Description

【問１】

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

(1) $M$ が受理する長さ 4 の文字列をすべて列挙せよ。

(2) $M$ が受理する言語 $L_1$ に含まれる文字列を説明せよ。

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

(4) 文字 $a$ で始まり文字 $b$ で終わる $\Sigma$ 上の文字列の集合を言語 $L_2$ とする。 言語 $L_1 \cap L_2$ を受理する状態数最小の決定性有限オートマトンの状態遷移図を与えよ。

【問２】

1+2+3 や 4+4−10 のように数の加減算を行う式を扱える、次の文脈自由文法 $G$ を考える。 文法 $G$ の終端記号は $0, 1, 2, 3, 4, 5, 6, 7, 8, 9, +, −$、非終端記号は $S, N, D$、開始記号は $S$ であり、生成規則は次の通りである。

$$\begin{aligned} S &\rightarrow N \mid S+N \mid S-N \\ N &\rightarrow D \mid DN \\ D &\rightarrow 0 \mid 1 \mid 2 \mid 3 \mid 4 \mid 5 \mid 6 \mid 7 \mid 8 \mid 9 \end{aligned}$$

開始記号 $S$ から生成規則に従った書換えにより導出できる文字列が、$G$ によって生成される文字列である。 例えば $G$ は文字列 4+4−10 を次の導出木により生成する。

次の各問い (1), (2) に答えよ。

(1) 次の各文字列は $G$ によって生成されるか。されるならば導出木を与え、されないならば理由を説明せよ。

• (a) 5+13+9
• (b) 25
• ($c$) 空文字列
• (d) -4+15

(2) $G$ は 05+3-0007 のように個々の数を表す部分の先頭に不要な 0 が付いた文字列も生成してしまう。 このような文字列が生成されないように修正した文法 $G'$ を考える。 文法 $G'$ の終端記号は $0, 1, 2, 3, 4, 5, 6, 7, 8, 9, +, −$、非終端記号は $S, N, M, D$、開始記号は $S$ であり、生成規則は次の通りである。 ただし $\varepsilon$ は空文字を表す。

$$\begin{aligned} S &\rightarrow N \mid S+N \mid S-N \\ N &\rightarrow 0 \mid \boxed{\ \ i \ \ } \\ M &\rightarrow \varepsilon \mid \boxed{\ \ ii \ \ } \mid \boxed{\ \ iii \ \ } \\ D &\rightarrow 1 \mid 2 \mid 3 \mid 4 \mid 5 \mid 6 \mid 7 \mid 8 \mid 9 \end{aligned}$$

$G'$ が意図通りになるよう空欄 $\boxed{\ \ i \ \ }$, $\boxed{\ \ ii \ \ }$, $\boxed{\ \ iii \ \ }$ を埋めよ。 ただし $G$ により生成される文字列のうち、排除したい文字列以外は、すべて $G'$ により生成されるようにすること。 また他の数字が直後に続かない単独の 0 が現れることは許すものとする。 $G'$ は例えば 0 や 1+301 や 0+0-203 を生成するが、00 や 1+0301 は生成しない。

题目描述

【问题 1】给定非确定性有限自动机 $M=(K,\Sigma,\delta,q_0,F)$，其中 $K=\{q_0,q_1\}$、$\Sigma=\{a,b\}$、初始状态为 $q_0$、终态集合 $F=\{q_0,q_1\}$，转移函数 $\delta$ 见原题状态迁移图。回答：

1. 枚举 $M$ 接受的所有长度为 $4$ 的字符串。
2. 记 $M$ 接受的语言为 $L_1$，描述 $L_1$ 中字符串的共同特征。
3. 画出接受 $L_1$ 且状态数最少的确定性有限自动机的状态迁移图。
4. 令 $L_2$ 为 $\Sigma$ 上所有以 $a$ 开头、以 $b$ 结尾的字符串组成的语言，画出接受交集语言 $L_1\cap L_2$ 且状态数最少的确定性有限自动机的状态迁移图。

【问题 2】考虑能表示数的加减算式（如 1+2+3、4+4−10）的上下文无关文法 $G$。其终结符为 $0,1,2,3,4,5,6,7,8,9,+,−$，非终结符为 $S,N,D$，开始符号为 $S$，产生式为

$$\begin{aligned} S &\rightarrow N \mid S+N \mid S-N, \\ N &\rightarrow D \mid DN, \\ D &\rightarrow 0 \mid 1 \mid 2 \mid 3 \mid 4 \mid 5 \mid 6 \mid 7 \mid 8 \mid 9. \end{aligned}$$

能从 $S$ 按产生式改写得到的字符串即为 $G$ 生成的字符串；原题以 4+4−10 的推导树为例。回答：

1. 分别判断下列字符串能否由 $G$ 生成；若能，画出推导树；若不能，说明理由：

   • (a) 5+13+9
   • (b) 25
   • (c) 空字符串
   • (d) -4+15

2. 文法 $G$ 还会生成 05+3-0007 这类在数值部分前带有多余 0 的字符串。现构造文法 $G'$ 排除它们：终结符仍为 $0,1,2,3,4,5,6,7,8,9,+,−$，非终结符为 $S,N,M,D$，开始符号为 $S$，且 $\varepsilon$ 表示空字符串，

   $$\begin{aligned} S &\rightarrow N \mid S+N \mid S-N, \\ N &\rightarrow 0 \mid \boxed{\ i\ }, \\ M &\rightarrow \varepsilon \mid \boxed{\ ii\ } \mid \boxed{\ iii\ }, \\ D &\rightarrow 1 \mid 2 \mid 3 \mid 4 \mid 5 \mid 6 \mid 7 \mid 8 \mid 9. \end{aligned}$$

   填写空格 $\boxed{\ i\ }$、$\boxed{\ ii\ }$、$\boxed{\ iii\ }$，使 $G'$ 恰好排除数值部分含无用前导零的情形，而 $G$ 生成的其他字符串仍全部可由 $G'$ 生成。允许不紧跟其他数字的单独 0：例如 $G'$ 应生成 0、1+301、0+0-203，但不能生成 00 或 1+0301。

Kai

【問１】

(1)

$$aaaa, aaab, aaba, abab, abaa, baaa, baba, baab$$

(2)

$b$ が連続しない文字列

(3)

(4)

【問２】

(1)

(a)

(b)

($c$)

生成されない。$N$ は少なくとも一桁の数字を生成し、$S$ は少なくとも一つの $N$ を含む式を生成するため、空文字列は得られない。

(d)

生成されない。$S$ が生成する式の先頭は必ず $N$ が生成する数字であり、単項の負号を置く規則はない。

(2)

• (i) DM
• (ii) NM
• (iii) DM

この解答の $M\to NM\mid DM\mid\varepsilon$ は冗長だが、$M$ が生成する言語は数字列全体である。$N\to0\mid DM$ により、数は単独の $0$ または非零の数字で始まる数に限られる。空欄 (ii) を $0M$ としても正しい。