Python - プログラムと機械 - 最も単純なコンピュータ - 決定性有限オートマン(シミュレーション)

アンダースタンディング コンピュテーション
(オライリージャパン)
Tom Stuart (著) 笹田 耕一(著) 笹井 崇司 (翻訳)
原書

開発環境

• OS X El Capitan - Apple (OS)
• Emacs(Text Editor)
• Python 3.5 (プログラミング言語)

アンダースタンディング コンピュテーション (Tom Stuart (著)、 笹田 耕一(著)、笹井 崇司 (翻訳)、オライリージャパン)の第1部(プログラムと機械)、3章(最も単純なコンピュータ)、3.1(決定性有限オートマン)、3.1.4(シミュレーション)を Python (本書ではRuby) で取り組んでみる。

3.1.4(シミュレーション)

コード(Emacs)

#!/usr/bin/env python3
# -*- coding: utf-8 -*-

class FARule:
    def __init__(self, state, character, next_state):
        self.state = state
        self.character = character
        self.next_state = next_state

    def is_applies_to(self, state, character):
        return self.state == state and self.character == character

    def follow(self):
        return self.next_state    

    def __repr__(self):
        return '#<FARule {0} --{1}--> {2}>'.format(
            repr(self.state), self.character, repr(self.next_state))

class DFARulebook:
    def __init__(self, rules):
        self.rules = rules

    def next_state(self, state, character):
        return self.rule_for(state, character).follow()

    def rule_for(self, state, character):
        for rule in self.rules:
            if rule.is_applies_to(state, character):
                return rule
        return None

class DFA:
    def __init__(self, current_state, accept_states, rulebook):
        self.current_state = current_state
        self.accept_states = accept_states
        self.rulebook = rulebook

    def is_accepting(self):
        return self.current_state in self.accept_states

    def read_character(self, character):
        self.current_state = self.rulebook.next_state(
            self.current_state, character)

    def read_string(self, string):
        for char in string:
            self.read_character(char)

class DFADesign:
    def __init__(self, start_state, accept_states, rulebook):
        self.start_state = start_state
        self.accept_states = accept_states
        self.rulebook = rulebook

    def to_dfa(self):
        return DFA(self.start_state, self.accept_states, self.rulebook)

    def is_accepts(self, string):
        dfa = self.to_dfa()
        dfa.read_string(string)
        return dfa.is_accepting()
    
if __name__ == '__main__':
    rulebook = DFARulebook([FARule(1, 'a', 2), FARule(1, 'b', 1),
                            FARule(2, 'a', 2), FARule(2, 'b', 3),
                            FARule(3, 'a', 3), FARule(3, 'b', 3)])
    print(rulebook)
    print(rulebook.next_state(1, 'a'))
    print(rulebook.next_state(1, 'b'))
    print(rulebook.next_state(2, 'b'))
    print()

    print(DFA(1, [1, 2], rulebook).is_accepting())
    print(DFA(1, [3], rulebook).is_accepting())
    print()
    
    dfa = DFA(1, [3], rulebook)
    print(dfa.is_accepting())
    dfa.read_character('b')
    print(dfa.is_accepting())
    for _ in range(3):
        dfa.read_character('a')
    print(dfa.is_accepting())
    dfa.read_character('b')
    print(dfa.is_accepting())
    print()

    dfa = DFA(1, [3], rulebook)
    print(dfa.is_accepting())
    dfa.read_string('baaab')
    print(dfa.is_accepting())
    print()

    dfa_design = DFADesign(1, [3], rulebook)
    print(dfa_design)
    print(dfa_design.is_accepts('a'))
    print(dfa_design.is_accepts('baa'))
    print(dfa_design.is_accepts('baba'))

入出力結果(Terminal, IPython)

$ ./sample1_4.py
<__main__.DFARulebook object at 0x10531ecc0>
2
1
3

True
False

False
False
False
True

False
True

<__main__.DFADesign object at 0x10531ecf8>
False
False
True
$