Kata

Your task is to convert εNFA/DFA to DFA and minimize.

It is assumed that you are familiar with the theory of automata and formal languages.

You can minimize DFA using different algorithms.
Minimal DFA for any εNFA/DFA is unique (except that the names of the states can be different).

Example (Sample test #4. Simple NFA).

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'}
   

In code:

"Input data"
fsm = {'0': {'a': {'1', '2'}, 'b': '2'},
       '1': {'a': '2', 'b': '3'},
       '2': {'a': {'1', '2'}, 'b': '3'},
       '3': {}}
initial_states = {'0'}
final_states = {'3'}

"Converting and minimizing (your implementation)"
new_dfa, new_initial_states, new_final_states = fsm_convert_and_minimize(fsm, initial_states, final_states)

"Checking result"
min_dfa == {'0': {'a': '1', 'b': '1'},
            '1': {'a': '1', 'b': '3'},
            '3': {}}
min_initial_states = {'0'}
min_final_states = {'3'}
is_dfa_isomorphic(min_dfa, min_initial_states, min_final_states, new_dfa, new_initial_states, new_final_states) -> True

Preloaded functions:

1. Function is_dfa_isomorphic(min_dfa, min_initial_states, min_final_states, dfa, initial_states, final_states). Compares two DFA's by isomorphism (not for all sufficient conditions, but for the main ones): whether the arguments are DFA's, whether the number of vertices (states) is equal, whether the number of arcs (transitions) is equal, whether the degrees of the vertices (states) are equal, as well as everything that the is_dfa_equals function checks.
   
2. Function is_dfa_equals(min_dfa, min_initial_states, min_final_states, dfa, initial_states, final_states). Compares two DFA's for equality by transitions and final states (return value can be True for DFA with different numbers of states, transitions, etc.).
   

Notes:

1. Vertices — states. Arcs — transitions. "Alpha" — transition label.
   
2. FSM with ε-transitions are also tested (U+03B5: 'ε'). Eliminate ε-transitions at the beginning.
   
3. 150 tests. 4 seconds — simple solution.
   
4. Recommendation: use Hopcroft's algorithm for minimization. It is used during testing.
   

Input data:
— εNFA/DFA: Dict[str, Dict[str, Union[str, Set[str]]]].
1 <= Number of transitions from each state <= Number of states <= 8.
— Initial states: Set[str].
0 <= Number of initial states <= 4.
— Final states: Set[str].
0 <= Number of final states <= 4.

Output data (tuple):
— Minimal DFA: Dict[str, Dict[str, str]].
— Initial states: Set[str].
— Final states: Set[str].
If the εNFA/DFA is empty or set of initial states is empty, then return (empty FSM, empty initial states, empty final states).

---

Also see @hapster100 katas:

1. Finite automation 1: DFA Runner
   
2. Finite automation 2: NFA Runner
   
3. Finite automation 3: Convert NFA to DFA
   

---

It might be easier to solve this problem with FSM autoplotting:

from typing import *


def to_flatten_tuple(any_arg: Any) -> Tuple[str]:
    import re
    return tuple(re.findall(pattern=r'\w+', string=str(any_arg)))


def fsm_plot(filename: str,
             fsm: Dict[Union[str, Tuple[str]],
                       Dict[str, Union[str, Tuple[str], Set[Union[str, Tuple[str]]]]]],
             initial_states: Union[str, Tuple[str],
                                   List[Union[str, Tuple[str]]], Set[Union[str, Tuple[str]]]],
             final_states: Union[str, Tuple[str],
                                 List[Union[str, Tuple[str]]], Set[Union[str, Tuple[str]]]]) -> None:
    import graphviz
    G = graphviz.Digraph()
    G.attr('graph', rankdir="LR")
    G.node('start', None, {'shape': 'point'})
    initial_states = set(initial_states) if isinstance(initial_states, (set, list)) else {initial_states}
    final_states = set(final_states) if isinstance(final_states, (set, list)) else {final_states}
    for state in fsm:
        G.attr('node', shape='doublecircle' if state in final_states else 'circle')
        G.node(','.join(state) if isinstance(state, tuple) else state)
    G.attr('node', shape='point')
    for state, alphas in fsm.items():
        if state in initial_states:
            G.edge(tail_name='start', head_name=state, label='')
        arcs = dict()
        for alpha, alpha_states in alphas.items():
            if isinstance(alpha_states, (str, tuple)):
                alpha_states = {alpha_states}
            for alpha_state in alpha_states:
                if state != alpha_state:
                    arcs.setdefault(alpha_state, set())
                    arcs[alpha_state].add(alpha)
        for alpha_state, alpha_state_alphas in arcs.items():
            G.edge(tail_name=','.join(state) if isinstance(state, tuple) else state,
                   head_name=','.join(alpha_state) if isinstance(alpha_state, tuple) else alpha_state,
                   label=','.join(sorted(alpha_state_alphas, key=to_flatten_tuple)))
        state_alpha_state = set()
        for alpha, alpha_states in alphas.items():
            if isinstance(alpha_states, (str, tuple)):
                alpha_states = {alpha_states}
            for alpha_state in alpha_states:
                if state == alpha_state:
                    state_alpha_state.add(alpha)
                    break
        if state_alpha_state:
            G.edge(tail_name=','.join(state) if isinstance(state, tuple) else state,
                   head_name=','.join(state) if isinstance(state, tuple) else state,
                   label=','.join(sorted(state_alpha_state, key=to_flatten_tuple)))
    G.render(filename, format='png', cleanup=True)