一覧CS-10-1 · 状態機械と言語

有限オートマトンと正規表現

文字列を一文字ずつ受け取る状態機械と、受理する文字列の規則を学びます。

説明

有限オートマトンは、有限個の状態と入力ごとの遷移規則を使って文字列を判定するモデルです。開始状態から一文字ずつ遷移し、全入力を使い切ったときに受理状態にいれば、その文字列を受理します。途中で受理状態を通過しただけでは決まりません。

aとbだけを使い、末尾がabの文字列を受理する機械を作ります。DFAでは現在状態が一つに決まり、NFAでは到達可能な複数の状態を集合で追います。最後に同じ規則の正規表現を使い、繰り返し記号と文字集合の範囲も調べます。

13状態の遷移表

Sは末尾がaでない状態、Aは末尾がa、Fは末尾がabです。開始はS、受理はFです。入力a・bのどちらにも次の状態を一つ決めます。

transition = {'S': {'a': 'A', 'b': 'S'}, 'A': {'a': 'A', 'b': 'F'}, 'F': {'a': 'A', 'b': 'S'}}状態と入力ごとの次状態; state = 'S'開始状態; transition遷移表

Aでaを読んでも末尾はaなのでAに残ります。Fで次のbを読むと末尾がabbになり、受理状態からSへ戻ります。有限の状態には入力全体ではなく判定に必要な末尾の情報を持たせています。

2aabを一文字ずつ処理

現在状態と入力文字で次状態を引き、処理の前後を表示します。

for letter in 'aab':左から一文字ずつ before = state処理前の状態 state = transition[state][letter]表から次状態を取得 print(before, letter, state)前状態・入力・後状態

S→A→A→Fとなり、全入力の後がFなので受理です。aが何回続いても最後にbが来れば末尾abになります。

3受理後にも入力が続く場合

さらにbを一つ読みます。入力全体はaabbになります。

accepted_before = state == 'F'追加前の受理判定; state = transition[state]['b']bをもう一つ読む; accepted_before, state, state == 'F'最終状態で判定

途中ではTrueでしたが、最後はSでFalseです。受理判定は最後に行うため、途中にabが含まれるだけでは条件を満たしません。

4独立した文字列を判定

文字列ごとに開始状態へ戻す関数を定義します。

def accepts(text):一つの文字列を判定 current = 'S'毎回開始状態へ for letter in text:全文字を処理 current = transition[current][letter]一意の次状態 return current == 'F'末尾で受理を判定

この関数は入力文字がa・bという条件で使います。前の文字列の最終状態を引き継がず、毎回Sから開始します。決定性有限オートマトンDFAでは各入力位置で現在状態が一つです。

5空文字と末尾の判定

空文字、ab、aba、baabを調べます。空文字では遷移がなく、開始状態Sのままです。

samples = ['', 'ab', 'aba', 'baab']判定する文字列; [(text, accepts(text)) for text in samples]DFAの結果

空文字とabaはFalse、abとbaabはTrueです。文字列の長さだけでなく、最後の2文字が判定を決めています。

6NFAでは到達可能な状態を集合にする

同じ末尾abを別の機械で表します。状態0は任意のa・bを読み続け、aで状態1へ進む枝も持ちます。状態1のbは受理状態2へ進みます。

nfa = {0: {'a': {0, 1}, 'b': {0}}, 1: {'a': set(), 'b': {2}}, 2: {'a': set(), 'b': set()}}状態ごとの行き先集合; active = {0}開始状態の集合; [(q, {c: sorted(dest) for c, dest in row.items()}) for q, row in nfa.items()]遷移表を順序固定で表示

0でaを読むと0と1の両方へ到達可能です。これはランダムにどちらかを選ぶ意味ではありません。入力を使い切った時点で受理状態へ至る経路が一つでもあれば受理します。

7全候補の行き先を合併

aabを読み、現在の全状態からの行き先の和集合を作ります。

for letter in 'aab':入力列 active = set().union(*(nfa[q][letter] for q in active))全候補の遷移先を合併 print(letter, sorted(active), 2 in active)文字・状態集合・受理候補

集合は{0,1}、{0,1}、{0,2}となり、最後に2を含むので受理です。状態集合を一つの状態とみなすと、DFAへの変換の考え方につながります。この例では空文字の遷移は使っていません。

8正規表現で同じ規則を指定

[ab]*はaまたはbの0回以上の繰り返しで、その後にabを要求します。fullmatchは文字列全体が一致するか調べます。

import re正規表現; pattern = r'[ab]*ab'a・bの繰り返しの後にab; [(text, re.fullmatch(pattern, text) is not None, accepts(text)) for text in samples + ['aab', 'abb']]正規表現とDFAを照合

正規表現とDFAの結果が一致します。searchで一部だけ探すとabb中のabにも一致するため、全文字列の受理と同じ条件にはなりません。

9繰り返し回数と文字集合

*は0回以上、+は1回以上、{2,3}は2回か3回です。[0-9]でASCIIの数字だけを指定したとき、全角数字は一致しません。

[(text, bool(re.fullmatch(r'[0-9]*', text)), bool(re.fullmatch(r'[0-9]+', text)), bool(re.fullmatch(r'[0-9]{2,3}', text))) for text in ['', '7', '42', '1234', '１２']]文字列ごとの0回以上・1回以上・2〜3回

空文字は*だけがTrue、42は全てTrue、1234は回数制限だけFalse、全角１２は全てFalseです。文字集合と繰り返し回数は別の条件として指定します。

まとめ

受理は全入力の処理後に判定します。途中で受理状態に入っても、その後の入力で外れることがあります。

DFAは現在状態一つ、NFAは到達可能な状態集合を追い、受理に至る経路の有無を調べます。

正規表現では文字集合・繰り返し・全体一致の条件を明示します。

操作履歴と解説を振り返れます。

Python 3

1
transition = {'S': {'a': 'A', 'b': 'S'}, 'A': {'a': 'A', 'b': 'F'}, 'F': {'a': 'A', 'b': 'S'}}; state = 'S'; transition
{'S': {'a': 'A', 'b': 'S'}, 'A': {'a': 'A', 'b': 'F'}, 'F': {'a': 'A', 'b': 'S'}}
2
for letter in 'aab': before = state state = transition[state][letter] print(before, letter, state)
S a A
A a A
A b F
3
accepted_before = state == 'F'; state = transition[state]['b']; accepted_before, state, state == 'F'
(True, 'S', False)
4
def accepts(text): current = 'S' for letter in text: current = transition[current][letter] return current == 'F'
5
samples = ['', 'ab', 'aba', 'baab']; [(text, accepts(text)) for text in samples]
[('', False), ('ab', True), ('aba', False), ('baab', True)]
6
nfa = {0: {'a': {0, 1}, 'b': {0}}, 1: {'a': set(), 'b': {2}}, 2: {'a': set(), 'b': set()}}; active = {0}; [(q, {c: sorted(dest) for c, dest in row.items()}) for q, row in nfa.items()]
[(0, {'a': [0, 1], 'b': [0]}), (1, {'a': [], 'b': [2]}), (2, {'a': [], 'b': []})]
7
for letter in 'aab':
    active = set().union(*(nfa[q][letter] for q in active))
    print(letter, sorted(active), 2 in active)
a [0, 1] False
a [0, 1] False
b [0, 2] True
8
import re; pattern = r'[ab]*ab'; [(text, re.fullmatch(pattern, text) is not None, accepts(text)) for text in samples + ['aab', 'abb']]
[('', False, False), ('ab', True, True), ('aba', False, False), ('baab', True, True), ('aab', True, True), ('abb', False, False)]
9
[(text, bool(re.fullmatch(r'[0-9]*', text)), bool(re.fullmatch(r'[0-9]+', text)), bool(re.fullmatch(r'[0-9]{2,3}', text))) for text in ['', '7', '42', '1234', '１２']]
[('', True, False, False), ('7', True, True, False), ('42', True, True, True), ('1234', True, True, False), ('１２', False, False, False)]
演習完了