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

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

開発環境

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

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

3.2.1(非決定性)

コード(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)

class NFA:
    def __init__(self, current_states, accept_states, rulebook):
        self.current_states = 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.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, 'a', 1), FARule(1, 'b', 1),
                            FARule(1, 'b', 2), FARule(2, 'a', 3),
                            FARule(2, 'b', 3), FARule(3, 'a', 4),
                            FARule(3, 'b', 4)])
    print(rulebook)
    print(rulebook.next_states({1}, 'b'))
    print(rulebook.next_states({1, 2}, 'a'))
    print(rulebook.next_states({1, 3}, 'b'))
    print()

    print(NFA({1}, [4], rulebook).is_accepting())
    print(NFA({1, 2, 4}, [4], rulebook).is_accepting())
    print()

    nfa = NFA({1}, [4], rulebook)
    print(nfa.is_accepting())
    nfa.read_character('b')
    print(nfa.is_accepting())
    nfa.read_character('a')
    print(nfa.is_accepting())
    nfa.read_character('b')
    print(nfa.is_accepting())
    nfa = NFA({1}, [4], rulebook)
    print(nfa)
    print(nfa.is_accepting())
    nfa.read_string('bbbbb')
    print(nfa.is_accepting())
    print()

    nfa_design = NFADesign(1, [4], rulebook)
    print(nfa_design)
    print(nfa_design.is_accepts('bab'))
    print(nfa_design.is_accepts('bbbbb'))
    print(nfa_design.is_accepts('bbabb'))

入出力結果(Terminal, IPython)

$ ./sample2_1.py
<__main__.NFARulebook object at 0x10daaada0>
{1, 2}
{1, 3}
{1, 2, 4}

False
True

False
False
False
True
<__main__.NFA object at 0x10daaae80>
False
True

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