Finite-State-Machine

Under development

Domain concepts

• State: State(uid: Hashable)
• Transition: Transition(label: Union[Hashable, None]) (None is Epsilon transition)
• FSM: FSM(fsm: Dict[State, Dict[Transition, Union[State, Set[State]]]], initial_states: Set[State], final_states: Set[State])
• Deterministic FSM: DeterministicFSM(fsm: Dict[State, Dict[Transition, State]], initial_states: Set[State], final_states: Set[State])

Algorithms

• Converting from Python Types: FSM.from_original(fsm: Dict[Hashable, Dict[Hashable, Union[Hashable, Set[Hashable]]]], initial_states: Set[Hashable], final_states: Set[Hashable])
• NFA to DFA conversion: DeterministicFSM.from_fsm(fsm_obj: FSM, name_of_state_generator)
• Elimination of epsilon-transitions: fsm.eliminate_epsilon_transitions()
• DFA Minimization by Hopcroft's Algorithm: dfsm.minimize(name_of_state_generator)
• FSM plotting (graphviz required): fsm.plot(filename)
• Random generation: FSM.generate(deterministic, states_alphabet, min_states, max_states, transitions_alphabet, min_transitions_from_state, max_transitions_from_state, min_initial_states, max_initial_states, min_final_states, max_final_states)

Example

1. NFA
   

NFA = {'0': {'a': {'1', '2'}, 'b': '2'},
       '1': {'a': '2', 'b': '3'},
       '2': {'a': {'1', '2'}, 'b': '3'},
       '3': {}}
initial_states = {'0'}
final_states = {'3'}

2. DFA
   

DFA = {'0': {'a': '1', 'b': '2'},
       '1': {'a': '1', 'b': '3'},
       '2': {'a': '1', 'b': '3'},
       '3': {}}
initial_states = {'0'}
final_states = {'3'}

3. Minimal DFA
   

Minimal_DFA = {'0': {'a': '1', 'b': '1'},
               '1': {'a': '1', 'b': '3'},
               '3': {}}
initial_states = {'0'}
final_states = {'3'}