この記事は東北大学計算機科学研究会 Advent Calendarの4日目の記事です。早くもネタ切れしてます。

授業でオートマトンをやったのと、有限オートマトンについて調べてみてもなかなかわかりやすい記事がないので書いてみることにしました。授業以前に本を読みつつ四苦八苦しながら理解したというのに、授業がとんでもなくわかりやすくて損した気分になりました。

まずザックリ実装してみる

有限オートマトンそのものを実装しても使い道はないです。しかし、理解の手助けにはなると思ったので書きました。DFAが「決定性有限オートマトン」、NFAが「非決定性有限オートマトン」です。

class DFA {
    constructor(alphabet, states, start, delta, finish) {
        this.alphabet = alphabet;
        this.states = states;
        this.state = start;
        this.delta = delta;
        this.finish = finish;
        this.accept = finish.includes(start);
    }
    input(x) {
        if (!this.alphabet.includes(x))
            throw new Error('received unknown alphabet.');
        this.state = this.delta(this.state, x);
        this.accept = this.finish.includes(this.state);
    }
}

const automaton = new DFA([0, 1], ['q0', 'q1'], 'q0', (s, x) => {
    switch (s) {
        case 'q0':
            return ['q1','q0'][x];
        case 'q1':
            return ['q0','q1'][x];
    }
}, ['q0']);

const automaton2 = new DFA(['a', 'b', 'c'], ['q0', 'q1', 'q2', 'q3'], 'q0', (s, x) => {
    switch (s) {
        case 'q0':
            return {a: 'q1', b: 'q2', c: 'q3'}[x];
        case 'q1':
            return {a: 'q1', b: 'q3', c: 'q3'}[x];
        case 'q2':
            return {a: 'q3', b: 'q2', c: 'q3'}[x];
        case 'q3':
            return {a: 'q3', b: 'q3', c: 'q3'}[x];
    }
}, ['q1', 'q2']);

for (const s of '10110') {
    automaton.input(parseInt(s, 10));
    console.log(automaton.state, automaton.accept);
}

for (const s of '0110111') {
    automaton2.input(parseInt(s, 10));
    console.log(automaton2.state, automaton2.accept);
}

オートマトンとは?

オートマトンとは、「1つだけ状態を持ち、入力を受け取り状態を変化させる機械」のことです。さっきのプログラムでいうstateが状態、inputの引数が入力です。

つまりこれと同じです。

const automaton = (s, input) => {
    if (s === 'xxx' && input === 'yyy') return 'zzz';
    if (s === 'xxx' && input === 'zzz') return 'xxx';
    // …
}
let state = startState;
state = automaton(state, input[0]);
state = automaton(state, input[1]);
state = automaton(state, input[2]);

オートマトンは現在の自身の状態と入力から、つぎの状態を決定しています。ReduxのReducerととても似ています。

そして、次に説明する「受理」こそが一番大切な概念です。

受理状態と非受理状態

オートマトンの状態には、「受理状態」と「非受理状態」があります。入力を受け付ける(受理)か受け付けない(非受理)かという文字通りの意味です。オートマトンは入力を受け、その入力を「受理」するか「非受理」するか決めます。しかし、非受理になったあとも、入力を受けて受理状態になることがあります。

入力をしていき、最終的に「受理状態」となったとき、その入力は「受理された」といいます。そして、受理される入力の集合を「正規言語」といいます。

「入力が受理されたかどうか判別する」ことがオートマトンの存在意義といっても過言ではありません。…いや、さすがに過言ですかね。

さっきの例に付け足すならこうですかね。

state = automaton(state, input[0]);
if (acceptList.includes(state)) console.log('accept!');
state = automaton(state, input[1]);
if (acceptList.includes(state)) console.log('accept!');
state = automaton(state, input[2]);
if (acceptList.includes(state)) console.log('accept!');

正規言語

受理される入力の集合を正規言語というといいました。では、はじめの実装に出てくるautomatonとautomaton2の正規言語はどうなるのでしょうか?

automatonに様々な入力をして観察してみます。

automaton.input(0); automaton.accept; // false
automaton.input(0); automaton.accept; // true
automaton.input(1); automaton.accept; // true
automaton.input(1); automaton.accept; // true
automaton.input(0); automaton.accept; // false
automaton.input(1); automaton.accept; // false
automaton.input(1); automaton.accept; // false
automaton.input(0); automaton.accept; // true

なんとなく見えてきました。automatonは「これまでに入力された0が偶数個なら受理する」オートマトンです。コードを読むと確かにあっていることが確認できます。

ではautomaton2も観察してみましょう。

automaton2.input('a'); automaton2.accept; // true
automaton2.input('a'); automaton2.accept; // true
automaton2.input('a'); automaton2.accept; // true
automaton2.input('b'); automaton2.accept; // false
automaton2.input('b'); automaton2.accept; // false
automaton2.input('c'); automaton2.accept; // false
automaton2.input('a'); automaton2.accept; // false
automaton2.input('a'); automaton2.accept; // false

// automaton2の状態を初期状態に戻す
automaton2.state = 'q0';
automaton2.input('b'); automaton2.accept; // true
automaton2.input('b'); automaton2.accept; // true
automaton2.input('b'); automaton2.accept; // true
automaton2.input('a'); automaton2.accept; // false
automaton2.input('c'); automaton2.accept; // false
automaton2.input('c'); automaton2.accept; // false
automaton2.input('b'); automaton2.accept; // false
automaton2.input('b'); automaton2.accept; // false

これは「これまでの入力がaのみまたはbのみの文字列」のとき受理します。

実はオートマトンと正規表現は密接な関係にあります。「なんで唐突に正規表現が出てくるんだ?」とお思いですよね。実は「正規言語を表すためのツールが正規表現」なのです*1。

例えば先の例ではautomatonは/(1*01*0)*/で、automaton2は/a+|b+/で表せます。

いろいろなオートマトン

7の倍数か判定するオートマトン

7の倍数を判定するオートマトンはつぎのようなアルゴリズムで作れます。

オートマトンの初期状態を0にする
入力を上の桁から読み込んでいく
現在の状態を10の位、入力を1の位にして、7で割ったあまりが次の遷移状態
最後まで読み込んだ時の状態があまり。0を受理状態とすれば判定できる

つまり、筆算です。筆算では、とりあえず1桁で割ろうとしてみて、だめならその下の桁と合わせた数を割る、ということを繰り返していきます。これをオートマトンで実装しただけです。

たとえば794を判定することを考えてみます。

0 * 10 + 7 を7で割ってあまり0(受理状態)
0 * 10 + 9を7で割ってあまり2(非受理状態)
2 * 10 + 4を7で割ってあまり3(非受理状態)

受理状態(0)にいないので、794は7の倍数ではありません。

さて、オートマトンを表す文字列が正規表現とさきほど述べました。ということは、オートマトンを正規表現に落とすことができます。実際にこれを利用して、「7の倍数を受理する正規言語」を書いた先人がいます。

「7の倍数」を表す正規表現 - Qiita

…まあ上の記事を読んでもらえばわかるとおり、普通にコードを書いたほうが楽です。コードゴルフに使える日は来るのでしょうか…

*1:実際にプログラミングで使う正規表現は本来の正規表現を拡張したものです

Panda Noir

JavaScript の限界を究めるブログでした。最近はいろんな分野を幅広めに書いてます。

有限オートマトンとはなんぞや