Skip to content

Instantly share code, notes, and snippets.

@utgwkk
Created October 17, 2016 06:10
Show Gist options
  • Save utgwkk/55c12b8f0b9a46bdda7cbc9847232c65 to your computer and use it in GitHub Desktop.
Save utgwkk/55c12b8f0b9a46bdda7cbc9847232c65 to your computer and use it in GitHub Desktop.
有限オートマトンの実装
class FiniteAutomata:
def __init__(self, alphas, transitions):
self.__state = 0
self.__alphas = set(alphas)
self.__transitions = transitions
def reset(self):
self.__state = 0
def readone(self, ch):
self.__state = self.__transitions[self.__state][ch]
def read(self, s):
for ch in s:
self.readone(ch)
def accepted(self):
return self.__transitions[self.__state].get('accepted', False)
if __name__ == '__main__':
fa = FiniteAutomata('01', [
{'0': 0, '1': 1, 'accepted': True},
{'0': 1, '1': 0},
{'0': 2, '1': 1},
])
for n in range(31):
fa.read('{:b}'.format(n))
print(n, '{:b}'.format(n), fa.accepted())
fa.reset()
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment