Panda Noir

JavaScript の限界を究めるブログです。

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

この記事は東北大学 計算機科学研究会 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) => {
    if (s === 'q0') return ['q1','q0'][x];
    if (s === 'q1') return ['q0','q1'][x];
}, ['q0']);
const automaton2 = new DFA(['a', 'b', 'c'], ['q0', 'q1', 'q2', 'q3'], 'q0', (s, x) => {
    if (s === 'q0') return {a: 'q1', b: 'q2', c: 'q3'}[x];
    if (s === 'q1') return {a: 'q1', b: 'q3', c: 'q3'}[x];
    if (s === 'q2') return {a: 'q3', b: 'q2', c: 'q3'}[x];
    if (s === '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]);

ただこれだけならすごくつまらないですよね。しかし、次に説明する「受理」がオートマトンにとって大切です。

受理する

オートマトンのキーワードとして「受理」というものがあります。オートマトンの状態には、「受理状態」と「非受理状態」があります。ある入力をして、最終的に「受理状態」となったとき、その入力は「受理された」といいます。受理される入力の集合を「正規言語」といいます。

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

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

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の倍数」を表す正規表現 - Qiita

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

いろいろなオートマトン

7の倍数を判定するオートマトンはつぎのような考え方で構築できます。

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

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

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

  1. 0 * 10 + 7 を7で割ってあまり0
  2. 0 * 10 + 9を7で割ってあまり2
  3. 2 * 10 + 4を7で割ってあまり3

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

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