Python - プログラムと機械 - 最も単純なコンピュータ - 非決定性有限オートマトン(自由移動)

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

開発環境

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

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

3.2.2(自由移動)

コード(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 NFARulebook:
    def __init__(self, rules):
        self.rules = rules

    def next_states(self, states, character):
        mapped = map(lambda state: self.follow_rules_for(state, character),
                     states)
        return set([x for l in mapped for x in l])

    def follow_rules_for(self, state, character):
        return map(lambda x: x.follow(), self.rules_for(state, character))

    def rules_for(self, state, character):
        return filter(lambda rule: rule.is_applies_to(state, character),
                      self.rules)

    def follow_free_moves(self, states):
        more_states = self.next_states(states, None)
        if more_states <= states:
            return states
        return self.follow_free_moves(states | more_states)

class NFA:
    def __init__(self, current_states, accept_states, rulebook):        
        self.current_states = rulebook.follow_free_moves(current_states)
        self.accept_states = accept_states
        self.rulebook = rulebook

    def is_accepting(self):
        return any(self.current_states & set(self.accept_states))

    def read_character(self, character):
        self.current_states = self.rulebook.next_states(
            self.rulebook.follow_free_moves(self.current_states), character)

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

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

    def is_accepts(self, string):
        nfa = self.to_nfa()
        nfa.read_string(string)
        return nfa.is_accepting()
    
    def to_nfa(self):
        return NFA({self.start_state}, self.accept_states, self.rulebook)    
    
if __name__ == '__main__':
    rulebook = NFARulebook([FARule(1, None, 2), FARule(1, None, 4),
                            FARule(2, 'a', 3), FARule(3, 'a', 2),
                            FARule(4, 'a', 5), FARule(5, 'a', 6),
                            FARule(6, 'a', 4)])
    print(rulebook)
    print(rulebook.next_states({1}, None))
    print()

    print(rulebook.follow_free_moves({1}))
    print()

    nfa_design = NFADesign(1, [2, 4], rulebook)
    print(nfa_design)
    print(nfa_design.is_accepts('aa'))
    print(nfa_design.is_accepts('aaa'))
    print(nfa_design.is_accepts('aaaaa'))
    print(nfa_design.is_accepts('aaaaaa'))

入出力結果(Terminal, IPython)

$ ./sample2_2.py
<__main__.NFARulebook object at 0x10efb9dd8>
{2, 4}

{1, 2, 4}

<__main__.NFADesign object at 0x10efb9e10>
True
True
False
True
$