Repository: caleb531/automata

Issue:
Conversion from DFA to NFA does not properly handle state names of mixed data types
I found the following bug:
nfa._add_new_state introduces integers into the set of states.

Current code is:
```
    def _add_new_state(state_set, start=0):
        """Adds new state to the state set and returns it"""
        new_state = start
        while new_state in state_set:
            new_state += 1

        state_set.add(new_state)

        return new_state
```
which could be fixed, for example, in this way:
```
    def _add_new_state(state_set, start=0):
        """Adds new state to the state set and returns it"""
        new_state = start
        while str(new_state) in state_set:
            new_state += 1

        state_set.add(str(new_state))

        return str(new_state)
```
EDIT: this bugfix actually runs into other problems later - this is just an idea
_____________________
This can lead to logic problems later. For example the following code fails:
```
from automata.fa.dfa import DFA
from automata.fa.nfa import NFA

A = NFA(
    states={'0', '1'},
    input_symbols={'0'},
    transitions={'0': {'0': {'1'}}, '1': {'0': {'1'}}},
    initial_state='0',
    final_states={'1'}
)

print(A.reverse().states)

B = DFA.from_nfa(A.reverse())

assert(A.accepts_input('00')==B.accepts_input('00'))
```

Discussion:
coveralls: 
[![Coverage Status](https://coveralls.io/builds/53118963/badge)](https://coveralls.io/builds/53118963)

Coverage remained the same at 100.0% when pulling **729ed8b40e5159b55d0518d8af25b9dbd7d7640a on eliotwrobson:nfa_conversion_fix** into **80987709928431572be930d9242968276c3845f7 on caleb531:develop**.

eliotwrobson: @caleb531 One thing to note is that this makes the DFA algorithms kindof inconsistent, since the others always convert merged state names to strings but `from_nfa` leaves them as tuples.
caleb531: > One thing to note is that this makes the DFA algorithms kindof inconsistent, since the others always convert merged state names to strings but from_nfa leaves them as frozensets.

@eliotwrobson Sure, but `NFA.from_dfa` was already creating state names (for the new NFA) as integers, regardless of the type of the original DFA's state names. Therefore, I suspect it's fine for the data type of the state names to change if the type of the instance is changing. Conversely, if the instance type is not changing, then the type of the state names should not change.

Going a step further, I wonder if it might be a good convention to enforce (in the `validate` method) that each individual `Automaton` sub-instance should not mix data types for its state names—they must all use the same data type. Kinda like the Python rule stipulating that you cannot mix spaces and tabs—it's an either/or choice (disregarding for a moment that PEP 8 prefers 4 spaces always, but you get my point).

In practice, this means that a DFA/NFA instance can only have state names of a single data type (e.g. str only, or int only, but never str mixed with int).

Would such a rule invalidate the need for this PR? Maybe, since the original situation from which this PR arose was your (somewhat contrived) example:

```python
A = NFA(
    states={1, '1'},
    input_symbols={'0'},
    transitions={1: {'0': {'1'}}, '1': {'0': {'1'}}},
    initial_state=1,
    final_states={'1'}
)

B = DFA.from_nfa(A)

assert A.accepts_input('00') == B.accepts_input('00')
```

But, if we stipulate that the above NFA must have either state names of all `str` type, OR state names of all `int` type, then this issue goes away, does it not?

Then again, tuples would probably be better than rigid string values, so I may still choose to accept this PR. But to your original point about the inconsistency, I'm thinking that the state name type is welcome to change when converting to another type of automaton (i.e. DFA->NFA or vice-versa).

Okay, thanks for listening to my sermon 😂😅. Thoughts?
eliotwrobson: You definitely bring up some valid points about consistency. In practice, I'm not sure how enforceable that convention is (for example, if state names can be tuples, do we enforce they all have the same length and same component types?).

In our fork, I already made the change to have all the DFA functions use tuples or frozensets for output state names, allowing mixed types for state names. This is because a bunch of the DFAs people construct in our course have mixed types for state names (since this is how a lot of our solutions are written). I'd recommend making the same change here, since it allows for more flexibility than enforcing one type for state names.

Although I raised the issue of inconsistency, I actually have a version of the tests using the tuples / frozensets as described (instead of converting to strings). I'd be happy to open a PR for that if you accept this one and go in that direction.
caleb531: @eliotwrobson I agree. But if we're going to do that, then we should also rewrite my recently-updated `NFA._add_new_state` (and possibly also `NFA.from_dfa`) to ensure that values like `1` (int) and `'1'` (str) are **not** considered equal.

Unless you think that would be too much of a footgun for people who might forget the quotes, but if we're moving away from string coercion, then I'd argue `1` and `'1'` _must_ be considered separate / not-equal.
eliotwrobson: > then we should also rewrite my recently-updated `NFA._add_new_state` (and possibly also `NFA.from_dfa`) to ensure that values like `1` (int) and `'1'` (str) are **_not_** considered equal.

I'm in agreement that the string and int versions should not be considered equal. I don't think it's that much of a footgun since it's more about setting a consistent convention than anything else (and the validation functions are there to prevent making inconsistent FAs).

I don't think these rewrites should be a big deal (and am happy to take them on), since I think we can just revert `NFA._add_new_state` to what it was before the rewrite, and `from_dfa` _should_ just work as written. Our fork is written with these assumptions in mind, so it's just a matter of copying things over on an as-needed basis.


caleb531: @eliotwrobson Okay, great! I was expecting the fix for `NFA._add_new_state` would effectively be reverting my changes to the method (you probably don't want to revert the entire commit dd9036683c9e46cde387bd0b98d5d3f4ebbb89b5 though, since it includes the additional test case for mixed state name types).

Thank you for your continued kindness in contributing so much code to this core library! I need to buy you a pizza or something. But yes, I'll gladly review any more PRs you send my way! 😄

Speaking of which, given our conversation here, did you have any more changes to make to this one before it's ready for my review?
eliotwrobson: @caleb531 no more changes to this one! I'll go ahead and take it out of draft. Once this is merged I'll put up the PR with the other rewrites. 

Patch:
diff --git a/README.md b/README.md
index 2941653..6431318 100644
--- a/README.md
+++ b/README.md
@@ -317,9 +317,10 @@ Returns `True` if the DFA accepts a finite language, False otherwise.
 dfa.isfinite()
 ```
 
-#### DFA.from_nfa(cls, nfa)
+#### DFA.from_nfa(cls, nfa, retain_names=False)
 
-Creates a DFA that is equivalent to the given NFA.
+Creates a DFA that is equivalent to the given NFA. States are renamed by
+default unless `retain_names` is set to `True`.
 
 ```python
 from automata.fa.dfa import DFA
diff --git a/automata/fa/dfa.py b/automata/fa/dfa.py
index 766bf8b..a6d5b3c 100644
--- a/automata/fa/dfa.py
+++ b/automata/fa/dfa.py
@@ -4,7 +4,7 @@
 import copy
 from collections import deque
 from enum import IntEnum
-from itertools import product
+from itertools import product, count
 
 import networkx as nx
 from pydot import Dot, Edge, Node
@@ -540,44 +540,61 @@ def _stringify_states(states):
         return '{{{}}}'.format(','.join(sorted(str(state) for state in states)))
 
     @classmethod
-    def from_nfa(cls, target_nfa):
+    def from_nfa(cls, target_nfa, retain_names=False):
         """Initialize this DFA as one equivalent to the given NFA."""
         dfa_states = set()
         dfa_symbols = target_nfa.input_symbols
-        dfa_transitions = dict()
+        dfa_transitions = {}
+
+        # Data structures for state renaming
+        new_state_name_dict = dict()
+        state_name_counter = count(0)
+
+        def get_name_renamed(states):
+            nonlocal state_name_counter, new_state_name_dict
+            return new_state_name_dict.setdefault(frozenset(states), next(state_name_counter))
+
+        def get_name_original(states):
+            return frozenset(states)
+
+        get_name = get_name_original if retain_names else get_name_renamed
 
         # equivalent DFA states states
         nfa_initial_states = target_nfa._get_lambda_closure(target_nfa.initial_state)
-        dfa_initial_state = cls._stringify_states(nfa_initial_states)
+        dfa_initial_state = get_name(nfa_initial_states)
         dfa_final_states = set()
 
         state_queue = deque()
         state_queue.append(nfa_initial_states)
         while state_queue:
             current_states = state_queue.popleft()
-            current_state_name = cls._stringify_states(current_states)
+            current_state_name = get_name(current_states)
             if current_state_name in dfa_states:
                 # We've been here before and nothing should have changed.
                 continue
 
+
             # Add NFA states to DFA as it is constructed from NFA.
             dfa_states.add(current_state_name)
             dfa_transitions[current_state_name] = {}
             if (current_states & target_nfa.final_states):
                 dfa_final_states.add(current_state_name)
 
+
             # Enqueue the next set of current states for the generated DFA.
             for input_symbol in target_nfa.input_symbols:
                 next_current_states = target_nfa._get_next_current_states(
                     current_states, input_symbol)
-                dfa_transitions[current_state_name][input_symbol] = cls._stringify_states(next_current_states)
+                dfa_transitions[current_state_name][input_symbol] = get_name(next_current_states)
                 state_queue.append(next_current_states)
 
+
         return cls(
             states=dfa_states, input_symbols=dfa_symbols,
             transitions=dfa_transitions, initial_state=dfa_initial_state,
             final_states=dfa_final_states)
 
+
     def show_diagram(self, path=None):
         """
             Creates the graph associated with this DFA


Test patch:
diff --git a/tests/test_dfa.py b/tests/test_dfa.py
index 52e3b9d..e51e2e8 100644
--- a/tests/test_dfa.py
+++ b/tests/test_dfa.py
@@ -1144,17 +1144,17 @@ def test_init_nfa_simple(self):
             initial_state='q0',
             final_states={'q2'}
         )
-        dfa = DFA.from_nfa(nfa)
-        self.assertEqual(dfa.states, {'{}', '{q0}', '{q0,q1}', '{q2}'})
+        dfa = DFA.from_nfa(nfa, retain_names=True)
+        self.assertEqual(dfa.states, {frozenset(), frozenset(('q0',)), frozenset(('q0','q1')), frozenset(('q2',))})
         self.assertEqual(dfa.input_symbols, {'0', '1'})
         self.assertEqual(dfa.transitions, {
-            '{}': {'0': '{}', '1': '{}'},
-            '{q0}': {'0': '{q0,q1}', '1': '{}'},
-            '{q0,q1}': {'0': '{q0,q1}', '1': '{q2}'},
-            '{q2}': {'0': '{}', '1': '{}'}
+            frozenset(): {'0': frozenset(), '1': frozenset()},
+            frozenset(('q0',)): {'0': frozenset(('q0','q1')), '1': frozenset()},
+            frozenset(('q0','q1')): {'0': frozenset(('q0','q1')), '1': frozenset(('q2',))},
+            frozenset(('q2',)): {'0': frozenset(), '1': frozenset()}
         })
-        self.assertEqual(dfa.initial_state, '{q0}')
-        self.assertEqual(dfa.final_states, {'{q2}'})
+        self.assertEqual(dfa.initial_state, frozenset(('q0',)))
+        self.assertEqual(dfa.final_states, {frozenset(('q2',))})
 
     def test_init_nfa_more_complex(self):
         """Should convert to a DFA a more complex NFA."""
@@ -1169,32 +1169,32 @@ def test_init_nfa_more_complex(self):
             initial_state='q0',
             final_states={'q2'}
         )
-        dfa = DFA.from_nfa(nfa)
+        dfa = DFA.from_nfa(nfa, retain_names=True)
         self.assertEqual(dfa.states, {
-            '{q0}', '{q0,q1}', '{q0,q2}', '{q0,q1,q2}'
+            frozenset(('q0',)), frozenset(('q0','q1')), frozenset(('q0','q2')), frozenset(('q0','q1','q2'))
         })
         self.assertEqual(dfa.input_symbols, {'0', '1'})
         self.assertEqual(dfa.transitions, {
-            '{q0}': {'1': '{q0}', '0': '{q0,q1}'},
-            '{q0,q1}': {'1': '{q0,q2}', '0': '{q0,q1}'},
-            '{q0,q2}': {'1': '{q0,q1}', '0': '{q0,q1,q2}'},
-            '{q0,q1,q2}': {'1': '{q0,q1,q2}', '0': '{q0,q1,q2}'}
+            frozenset(('q0',)): {'1': frozenset(('q0',)), '0': frozenset(('q0','q1'))},
+            frozenset(('q0','q1')): {'1': frozenset(('q0','q2')), '0': frozenset(('q0','q1'))},
+            frozenset(('q0','q2')): {'1': frozenset(('q0','q1')), '0': frozenset(('q0','q1','q2'))},
+            frozenset(('q0','q1','q2')): {'1': frozenset(('q0','q1','q2')), '0': frozenset(('q0','q1','q2'))}
         })
-        self.assertEqual(dfa.initial_state, '{q0}')
-        self.assertEqual(dfa.final_states, {'{q0,q1,q2}', '{q0,q2}'})
+        self.assertEqual(dfa.initial_state, frozenset(('q0',)))
+        self.assertEqual(dfa.final_states, {frozenset(('q0','q1','q2')), frozenset(('q0','q2'))})
 
     def test_init_nfa_lambda_transition(self):
         """Should convert to a DFA an NFA with a lambda transition."""
-        dfa = DFA.from_nfa(self.nfa)
-        self.assertEqual(dfa.states, {'{}', '{q0}', '{q1,q2}'})
+        dfa = DFA.from_nfa(self.nfa, retain_names=True)
+        self.assertEqual(dfa.states, {frozenset(), frozenset(('q0',)), frozenset(('q1', 'q2'))})
         self.assertEqual(dfa.input_symbols, {'a', 'b'})
         self.assertEqual(dfa.transitions, {
-            '{}': {'a': '{}', 'b': '{}'},
-            '{q0}': {'a': '{q1,q2}', 'b': '{}'},
-            '{q1,q2}': {'a': '{q1,q2}', 'b': '{q0}'},
+            frozenset(): {'a': frozenset(), 'b': frozenset()},
+            frozenset(('q0',)): {'a': frozenset(('q1', 'q2')), 'b': frozenset()},
+            frozenset(('q1', 'q2')): {'a': frozenset(('q1', 'q2')), 'b': frozenset(('q0',))},
         })
-        self.assertEqual(dfa.initial_state, '{q0}')
-        self.assertEqual(dfa.final_states, {'{q1,q2}'})
+        self.assertEqual(dfa.initial_state, frozenset(('q0',)))
+        self.assertEqual(dfa.final_states, {frozenset(('q1', 'q2'))})
 
     def test_nfa_to_dfa_with_lambda_transitions(self):
         """ Test NFA->DFA when initial state has lambda transitions """
@@ -1209,8 +1209,8 @@ def test_nfa_to_dfa_with_lambda_transitions(self):
             initial_state='q0',
             final_states={'q1'}
         )
-        dfa = DFA.from_nfa(nfa)  # returns an equivalent DFA
-        self.assertEqual(dfa.read_input('a'), '{q1}')
+        dfa = DFA.from_nfa(nfa, retain_names=True)  # returns an equivalent DFA
+        self.assertEqual(dfa.read_input('a'), frozenset(('q1',)))
 
     def test_partial_dfa(self):
         """Should allow for partial DFA when flag is set"""