Repository: caleb531/automata

Issue:
Bug in read_input_as_ntm() in MNTM implementation
Hey @caleb531!

I was just checking out the library and found the following bug. I took the `mntm3` from [automata](https://github.com/caleb531/automata/tree/main)/[tests](https://github.com/caleb531/automata/tree/main/tests)
/[test_tm.py](https://github.com/caleb531/automata/blob/main/tests/test_tm.py), which is the following:

```python
from automata.tm.mntm import MNTM

# MNTM which accepts all strings of the form ww, where w is in {0, 1}*
mntm = MNTM(
    states={"q0", "q1", "q2", "q3", "q4"},
    input_symbols={"0", "1"},
    tape_symbols={"0", "1", "$", "#"},
    n_tapes=3,
    transitions={
        "q0": {
            ("0", "#", "#"): [("q1", (("0", "N"), ("$", "R"), ("$", "R")))],
            ("1", "#", "#"): [("q1", (("1", "N"), ("$", "R"), ("$", "R")))],
        },
        "q1": {
            ("0", "#", "#"): [
                ("q1", (("0", "R"), ("0", "R"), ("#", "N"))),
                ("q2", (("0", "R"), ("#", "N"), ("0", "R"))),
            ],
            ("1", "#", "#"): [
                ("q1", (("1", "R"), ("1", "R"), ("#", "N"))),
                ("q2", (("1", "R"), ("#", "N"), ("1", "R"))),
            ],
        },
        "q2": {
            ("0", "#", "#"): [("q2", (("0", "R"), ("#", "N"), ("0", "R")))],
            ("1", "#", "#"): [("q2", (("1", "R"), ("#", "N"), ("1", "R")))],
            ("#", "#", "#"): [("q3", (("#", "N"), ("#", "L"), ("#", "L")))],
        },
        "q3": {
            ("#", "0", "0"): [("q3", (("#", "N"), ("0", "L"), ("0", "L")))],
            ("#", "1", "1"): [("q3", (("#", "N"), ("1", "L"), ("1", "L")))],
            ("#", "$", "$"): [("q4", (("#", "N"), ("$", "N"), ("$", "N")))],
        },
    },
    initial_state="q0",
    blank_symbol="#",
    final_states={"q4"},
)
```
And I ran it as a multi-tape TM and as a single-tape. As the former, it returns `True` correctly for the cases: `11`, `00`, `1010`, `0101`, etc., but when you run it as a single-tape, it gets a `RejectionException: the multitape NTM did not reach an accepting configuration`.

```python
print(mntm.accepts_input("0101")) # This correctly returns True

for conf in mntm.read_input_as_ntm("0101"): # This will throw the exception
    print(conf)
```

I am using `automata-lib v8.4.0`.

**Full Traceback**
```python
---------------------------------------------------------------------------
KeyError                                  Traceback (most recent call last)
File c:\Users\camil\Documents\Repositorios\automata\.venv\Lib\site-packages\automata\tm\mntm.py:379, in MNTM.read_input_as_ntm(self, input_str)
    [378](file:///C:/Users/camil/Documents/Repositorios/automata/.venv/Lib/site-packages/automata/tm/mntm.py:378) try:
--> [379](file:///C:/Users/camil/Documents/Repositorios/automata/.venv/Lib/site-packages/automata/tm/mntm.py:379)     next_config = self.transitions[current_state][virtual_heads]
    [380](file:///C:/Users/camil/Documents/Repositorios/automata/.venv/Lib/site-packages/automata/tm/mntm.py:380) except KeyError:

KeyError: ('#', '#', '#')

During handling of the above exception, another exception occurred:

RejectionException                        Traceback (most recent call last)
Cell In[11], [line 42](vscode-notebook-cell:?execution_count=11&line=42)
      [4](vscode-notebook-cell:?execution_count=11&line=4) mntm = MNTM(
      [5](vscode-notebook-cell:?execution_count=11&line=5)     states={"q0", "q1", "q2", "q3", "q4"},
      [6](vscode-notebook-cell:?execution_count=11&line=6)     input_symbols={"0", "1"},
   (...)
     [37](vscode-notebook-cell:?execution_count=11&line=37)     final_states={"q4"},
     [38](vscode-notebook-cell:?execution_count=11&line=38) )
     [40](vscode-notebook-cell:?execution_count=11&line=40) print(mntm.accepts_input("1111"))
---> [42](vscode-notebook-cell:?execution_count=11&line=42) for conf in mntm.read_input_as_ntm("1111"):
     [43](vscode-notebook-cell:?execution_count=11&line=43)     print(conf)

File c:\Users\camil\Documents\Repositorios\automata\.venv\Lib\site-packages\automata\tm\mntm.py:381, in MNTM.read_input_as_ntm(self, input_str)
    [379](file:///C:/Users/camil/Documents/Repositorios/automata/.venv/Lib/site-packages/automata/tm/mntm.py:379)     next_config = self.transitions[current_state][virtual_heads]
    [380](file:///C:/Users/camil/Documents/Repositorios/automata/.venv/Lib/site-packages/automata/tm/mntm.py:380) except KeyError:
--> [381](file:///C:/Users/camil/Documents/Repositorios/automata/.venv/Lib/site-packages/automata/tm/mntm.py:381)     raise exceptions.RejectionException(
    [382](file:///C:/Users/camil/Documents/Repositorios/automata/.venv/Lib/site-packages/automata/tm/mntm.py:382)         "the multitape NTM did not reach an accepting configuration"
    [383](file:///C:/Users/camil/Documents/Repositorios/automata/.venv/Lib/site-packages/automata/tm/mntm.py:383)     )
    [384](file:///C:/Users/camil/Documents/Repositorios/automata/.venv/Lib/site-packages/automata/tm/mntm.py:384) next_state, moves = next_config[0]
    [385](file:///C:/Users/camil/Documents/Repositorios/automata/.venv/Lib/site-packages/automata/tm/mntm.py:385) for move in moves:

RejectionException: the multitape NTM did not reach an accepting configuration
```
I can take it a look at it myself in the following week, so I thought to leave it here so as not to forget it :)

Discussion:
@eliotwrobson: Seems reasonable! Thanks @CamiloMartinezM for pointing this out. I'm busy with other projects right now, but if you put up a PR with a fix for this I am happy to review.@eliotwrobson: PR with a fix for this just merged to develop.

Solution patch:
diff --git a/.vscode/extensions.json b/.vscode/extensions.json
index 71baa4a7..2d61eba5 100644
--- a/.vscode/extensions.json
+++ b/.vscode/extensions.json
@@ -2,6 +2,7 @@
   "recommendations": [
     "EditorConfig.EditorConfig",
     "ms-python.black-formatter",
+    "ms-python.isort",
     "matangover.mypy",
     "ms-python.flake8"
   ]
diff --git a/.vscode/settings.json b/.vscode/settings.json
index 1951422f..91aad60a 100644
--- a/.vscode/settings.json
+++ b/.vscode/settings.json
@@ -3,6 +3,7 @@
   "[python]": {
     "editor.formatOnSave": true,
     "editor.defaultFormatter": "ms-python.black-formatter",
+    "editor.rulers": [88],
     "editor.codeActionsOnSave": {
       "source.organizeImports": "explicit"
     }
diff --git a/automata/tm/mntm.py b/automata/tm/mntm.py
index 921faad3..be47da51 100644
--- a/automata/tm/mntm.py
+++ b/automata/tm/mntm.py
@@ -352,87 +352,88 @@ def read_input_as_ntm(
         tape_separator_symbol = "_"
 
         # Make string from all tapes
-        extended_tape = "".join(
+        initial_tape = "".join(
             chain.from_iterable(
                 (tape.tape[0], head_symbol, *tape.tape[1:], tape_separator_symbol)
                 for tape in tapes
             )
         )
 
-        current_state = self.initial_state
-        yield {
-            TMConfiguration(
+        # Use a queue for BFS to handle non-determinism
+        # (state, tape, position)
+        queue = deque([(self.initial_state, initial_tape, 0)])
+
+        while queue:
+            current_state, extended_tape, pos = queue.popleft()
+            current_config = TMConfiguration(
                 current_state,
                 TMTape(
-                    extended_tape, blank_symbol=self.blank_symbol, current_position=0
+                    extended_tape, blank_symbol=self.blank_symbol, current_position=pos
                 ),
             )
-        }
 
-        # If the machine has not reached an accepting state.
-        while current_state not in self.final_states:
-            i = 0  # current position
+            yield {current_config}
+
+            if current_state in self.final_states:
+                return
+
+            # Read virtual heads from the tape
             virtual_heads = self._read_extended_tape(
                 extended_tape, head_symbol, tape_separator_symbol
             )
+
+            # Get all possible transitions
             try:
-                next_config = self.transitions[current_state][virtual_heads]
+                possible_configs = self.transitions[current_state][virtual_heads]
             except KeyError:
-                raise exceptions.RejectionException(
-                    "the multitape NTM did not reach an accepting configuration"
-                )
-            next_state, moves = next_config[0]
-            for move in moves:
-                new_head, direction = move
-                executing_changes = True
-
-                while executing_changes:
-                    if extended_tape[i] == head_symbol:
-                        # Head has been found (previous symbol is the head).
-                        # This replaces the previous symbol with the new_head.
-                        extended_tape = (
-                            extended_tape[: i - 1] + new_head + extended_tape[i:]
-                        )
-                        extended_tape = extended_tape[:i] + "" + extended_tape[i + 1 :]
-
-                        # After replacing, the machine must change the
-                        # position of the virtual head of the current virtual
-                        # tape.
-                        if direction == "R":
-                            i += 1
-                        elif direction == "L":
-                            i -= 1
-                        else:  # direction == 'N'
-                            i += 0
-
-                        if extended_tape[i - 1] == tape_separator_symbol:
-                            i -= 1
-                            extended_tape = (
-                                extended_tape[:i]
-                                + self.blank_symbol
-                                + head_symbol
-                                + extended_tape[i:]
-                            )
-
-                            i += 1
-                        else:
-                            extended_tape = (
-                                extended_tape[:i] + head_symbol + extended_tape[i:]
-                            )
-
-                    elif extended_tape[i] == tape_separator_symbol:
-                        executing_changes = False
-
-                    i += 1
-
-            current_state = next_state
-            yield {
-                TMConfiguration(
-                    current_state,
-                    TMTape(
-                        extended_tape,
-                        blank_symbol=self.blank_symbol,
-                        current_position=i - 1,
-                    ),
-                )
-            }
+                continue  # No valid transition, try other paths
+
+            # Process each possible next configuration
+            for next_config in possible_configs:
+                next_state, moves = next_config
+                new_tape = extended_tape
+                i = 0  # current position
+
+                # Apply the moves to get the next tape configuration
+                for move in moves:
+                    new_head, direction = move
+                    executing_changes = True
+
+                    while executing_changes:
+                        if new_tape[i] == head_symbol:
+                            # Update the tape symbol before the head
+                            new_tape = new_tape[: i - 1] + new_head + new_tape[i:]
+                            # Remove the old head
+                            new_tape = new_tape[:i] + "" + new_tape[i + 1 :]
+
+                            # Move the head according to direction
+                            if direction == "R":
+                                i += 1
+                            elif direction == "L":
+                                i -= 1
+                            # else direction == 'N', i stays the same
+
+                            # Handle edge cases with tape separator
+                            if i > 0 and new_tape[i - 1] == tape_separator_symbol:
+                                i -= 1
+                                new_tape = (
+                                    new_tape[:i]
+                                    + self.blank_symbol
+                                    + head_symbol
+                                    + new_tape[i:]
+                                )
+                                i += 1
+                            else:
+                                new_tape = new_tape[:i] + head_symbol + new_tape[i:]
+
+                        elif new_tape[i] == tape_separator_symbol:
+                            executing_changes = False
+
+                        i += 1
+
+                # Add the new configuration to the queue
+                queue.append((next_state, new_tape, i - 1))
+
+        raise exceptions.RejectionException(
+            "the multitape NTM did not reach an accepting configuration"
+        )


Test patch:
diff --git a/tests/test_mntm.py b/tests/test_mntm.py
index 3233e29e..0b892c8c 100644
--- a/tests/test_mntm.py
+++ b/tests/test_mntm.py
@@ -4,6 +4,7 @@
 import math
 import random
 import types
+from typing import Set, cast
 from unittest.mock import MagicMock, patch
 
 from frozendict import frozendict
@@ -393,10 +394,51 @@ def test_read_input_as_ntm(self) -> None:
             str(last_config.tape), "TMTape('#0000#^_#0000#^_#XYYY#^_', '#', 23)"
         )
 
+        # Test that it throws a RejectionException
         with self.assertRaises(exceptions.RejectionException):
             for _ in self.mntm2.read_input_as_ntm("#00"):
                 pass
 
+        # Thoroughly test the MNTM as an NTM and check that the final tapes are the same
+        # regardless of whether the MNTM is run as an NTM or an MNTM
+        mntms = [self.mntm1, self.mntm2, self.mntm3]
+        inputs = ["0110", "#0000", "0101"]
+
+        for mntm, input_str in zip(mntms, inputs):
+            # Test that it doesn't throw a RejectionException
+            self.assertTrue(mntm.accepts_input(input_str))
+            configs = list(mntm.read_input_stepwise(input_str))
+            final_mntm_config = cast(Set, configs[-1]).pop()
+
+            # Test that the final tape of the MNTM is the same as the final tape of the
+            # MNTM ran as an NTM.
+            # First, join the tapes of the MNTM, as they would (and should) be in the
+            # NTM version ^ being the head symbol, _ being the tape separator
+            final_mntm_tape = ""
+            for tape in final_mntm_config.tapes:
+                curr_tape = "".join(tape.tape)
+
+                # Add a ^ after the current position, for the head symbol
+                curr_tape_pos = tape.current_position + 1
+
+                # For self.mntm1 with input 0110, the final tape of the MNTM should be
+                # 0110#^_11#^_ in the end as a result of concatenating:
+                # MTMConfig... ('q1', (TMTape('0110#', '#', 4), TMTape('11#', '#', 2)))
+                final_mntm_tape += (
+                    curr_tape[:curr_tape_pos] + "^" + curr_tape[curr_tape_pos:] + "_"
+                )
+
+            # Now, run the MNTM as an NTM
+            configs = list(mntm.read_input_as_ntm(input_str))
+            final_ntm_config = cast(Set, configs[-1]).pop()
+
+            # e.g., 0110#^_11#^_ for self.mntm1 with input 0110 as a result of:
+            # TMConfiguration('q1', TMTape('0110#^_11#^_', '#', 11))
+            final_ntm_tape = "".join(final_ntm_config.tape.tape)
+
+            # Finally, assert that the final tapes are the same
+            self.assertEqual(final_mntm_tape, final_ntm_tape)
+
     def test_read_input_accepted(self) -> None:
         """Should return correct state if acceptable TM input is given."""
         final_config = self.mntm1.read_input("0101101011").pop()