1と2のボタンだけの錠
有限オートマトンとは、決まった数の状態を持ち、入力を1文字ずつ読んで受理か拒否かを答える、最も単純な計算の機械です。自動改札や錠のように、順番に押すものの設計に使われます。
ボタンが1と2だけの錠を考えます。1、2の順に続けて押すと開く錠は、何を覚えていればよいでしょうか。答えは、直前に1を押したかどうかです。
このレッスンのゴール
メモ
遷移表をたどって、有限オートマトンがある文字列を受理するかどうか言える。
重要な言葉
| ことば | いみ |
|---|---|
| 状態 | 機械が今いる場所。覚えていることのすべて |
| 遷移 | 文字を1つ読んで、次の状態へ移ること |
| 遷移表 | 状態と文字から、次の状態を決める表 |
| 初期状態 | 読み始める前にいる状態 |
| 受理状態 | 読み終えたときここにいれば受け入れる状態 |
| 受理 | 機械が文字列を正しいと認めること |
学生が入力するセルは、このプレビューでは空白です。
機械は状態を1つずつ移る
機械は、いつも状態のどれか1つにいます。文字を1つ読むたびに、遷移表に従って次の状態へ移ります。
錠の状態は3つです。何もない「待ち」、1を押した「1押した」、開いた「開く」。覚えているのは、この3つだけです。
2112 を読むと
| 読む文字 | 前の状態 | 次の状態 |
|---|---|---|
| 2 | 待ち | 待ち |
| 1 | 待ち | 1押した |
| 1 | 1押した | 1押した |
| 2 | 1押した | 開く |
| 読み終わり | 開く | 受理する |
学生が入力するセルは、このプレビューでは空白です。
錠を動かす Python
# 1、2の順に押すと開く錠。状態は3つです。
table = {
"wait": {"1": "one", "2": "wait"},
"one": {"1": "one", "2": "open"},
"open": {"1": "open", "2": "open"},
}
text = "2112" # ここを "2211" に変えて、もう一度実行しましょう。
state = "wait"
for ch in text:
state = table[state][ch]
print(ch, "を読んで", state)
print("受理:", state == "open")
受理は最後の状態で決まる
文字をすべて読み終えたとき、受理状態にいれば受理です。いなければ拒否です。途中で通った状態は関係ありません。
何も読まない空の文字列も、初期状態が受理状態なら受理されます。表にない文字が来たときも、拒否と決めておきます。
ラボで同じ錠を動かす
同じ錠を、ラボの端末で動かします。1つ目の Run は lock.py というファイルを作るだけで、画面には何も出しません。
2つ目と3つ目は、押した順を引数に渡して、1文字ごとの状態を出します。最後の行が True なら受理です。
錠のファイルを作る
printf 'import sys\ntable = {"wait": {"1": "one", "2": "wait"}, "one": {"1": "one", "2": "open"}, "open": {"1": "open", "2": "open"}}\nstate = "wait"\nfor ch in sys.argv[1]:\n state = table[state][ch]\n print(ch, state)\nprint(state == "open")\n' > lock.pyここでは表示のみで、実行されません。無料アカウントを作成すると、実行ボタンで自分のラボのターミナルに入力できます。
2112 を押す
python3 lock.py 2112ここでは表示のみで、実行されません。無料アカウントを作成すると、実行ボタンで自分のラボのターミナルに入力できます。
2211 を押す
python3 lock.py 2211ここでは表示のみで、実行されません。無料アカウントを作成すると、実行ボタンで自分のラボのターミナルに入力できます。
よくある間違い
注意
途中で受理状態を通れば受理、と思いがちです。そうではなく、受理かどうかは読み終えた状態だけで決まります。偶数個の1を受理する機械は、111 を読む途中で一度受理状態を通りますが、最後は奇数なので拒否です。
なぜ「有限」なのか
状態の数は決まっています。だから、1を何個読んだかを、いくつでも数え続けることはできません。
1が偶数個か奇数個かなら、2つの状態で覚えられます。この「覚えられる量に限りがある」ことが、次のレッスン以降の話の土台です。
さらに挑戦: 3の倍数の機械
2進数の文字列が、3の倍数かどうかを調べる機械を作れます。状態は3つで、「3で割った余り」が0、1、2の場合です。
遷移表を紙に書き、run_dfa に渡して、"110"（6）が受理され、"101"（5）が拒否されることを確かめましょう。