東京工業大学 情報理工学院 情報工学系 2016年8月実施 午前 2.

标签：

• institute-of-science-tokyo
• Deterministic-Finite-Automaton

Author

祭音Myyura (co-authored with GPT 5.6 SOL)

Description

$\Sigma=\{0,1\}$ とし、二進整数を最上位ビットから入力する。先頭の $0$ は許し、空語は扱わない。状態遷移は行を状態、列を入力記号とする表で答えよ。

例 $A_0$ は $Q=\{q_0,q_1\}$、初期状態 $q_0$、受理集合 $\{q_0\}$ とし、両入力で $q_0,q_1$ を交互に移る、偶数長の語を受理する DFA である。

1. $A_0$ の遷移関数だけを変更し、偶数を受理する2状態 DFA $A_1$ を与えよ。
2. $A_1$ を奇数だけ受理するものに変更する方法を30字以内で答えよ。
3. $Q=\{r_0,r_1,r_2\}$、初期状態 $r_0$ の3状態 DFA $A_2$ で3の倍数だけを受理せよ。
4. $A_1,A_2$ の積により、6の倍数だけ受理する6状態 DFA $A_3$ を定義し、状態の対応を60字以内で説明せよ。
5. $A_1,A_2$ の和により、偶数または3の倍数を受理する6状態 NFA $A_4$ を、初期状態 $s_0$ として定義せよ。状態の対応を60字以内で説明せよ。
6. $A_4$ と等価な DFA $A_5$ を初期状態 $s_0$ として定義し、状態の対応を120字以内で説明せよ。

题目描述

构造识别二进制偶数、奇数、3的倍数、6的倍数的自动机；用非确定自动机实现“偶数或3的倍数”，再确定化。允许前导零，不处理空串。

Kai

1)

$\delta_1$	0	1
$q_0$	$q_0$	$q_1$
$q_1$	$q_0$	$q_1$

2)

受理状態の集合を $\{q_1\}$ に変更する。

3)

$F_2=\{r_0\}$。$r_j$ は読んだ整数の3での剰余 $j$ を表す。

$\delta_2$	0	1
$r_0$	$r_0$	$r_1$
$r_1$	$r_2$	$r_0$
$r_2$	$r_1$	$r_2$

入力 $b$ により剰余は $(2j+b)\bmod3$ となる。

4)

状態 $p_{ij}=(q_i,r_j)$、初期状態 $p_{00}$、$F_3=\{p_{00}\}$ とする。

$\delta_3$	0	1
$p_{00}$	$p_{00}$	$p_{11}$
$p_{01}$	$p_{02}$	$p_{10}$
$p_{02}$	$p_{01}$	$p_{12}$
$p_{10}$	$p_{00}$	$p_{11}$
$p_{11}$	$p_{02}$	$p_{10}$
$p_{12}$	$p_{01}$	$p_{12}$

$p_{ij}$ は $A_1$ が $q_i$、$A_2$ が $r_j$ にある状態を表す。

5)

$Q_4=\{s_0,q_0,q_1,r_0,r_1,r_2\}$、$F_4=\{q_0,r_0\}$ とする。

$\delta_4$	0	1
$s_0$	$\{q_0,r_0\}$	$\{q_1,r_1\}$
$q_0$	$\{q_0\}$	$\{q_1\}$
$q_1$	$\{q_0\}$	$\{q_1\}$
$r_0$	$\{r_0\}$	$\{r_1\}$
$r_1$	$\{r_2\}$	$\{r_0\}$
$r_2$	$\{r_1\}$	$\{r_2\}$

最初の入力で両機械に分岐し、その後は各機械の遷移を行う。

6)

$Q_5=\{s_0\}\cup\{p_{ij}:0\le i\le1,\ 0\le j\le2\}$ とし、$p_{ij}$ からの遷移は4)の表と同じとする。追加の行は

$\delta_5$	0	1
$s_0$	$p_{00}$	$p_{11}$

受理集合は

$$F_5=\{p_{00},p_{01},p_{02},p_{10}\}.$$

$p_{ij}$ は NFA の状態集合 $\{q_i,r_j\}$ に対応する。いずれかの成分が受理状態なら受理する。$s_0$ は入力前だけの状態である。