States Transitioning: Simulate a Finite State Machine and Detect Reachable States

Question

## Problem

You are given a finite state machine (FSM) defined by a set of states, an alphabet, a transition table, a start state, and a set of accepting states. Given an input string, determine whether the FSM accepts it. Also implement a method that returns all states reachable from the start state.

```python
class FSM:
    def __init__(self,
                 states: set[str],
                 alphabet: set[str],
                 transitions: dict[tuple[str,str], str],  # (state, symbol) -> state
                 start: str,
                 accepting: set[str]):
        ...

def accepts(self, input_str: str) -> bool: ...
    def reachable_states(self) -> set[str]: ...
```

**Example:**
```
# FSM that accepts strings ending in 'b'
transitions = {('q0','a'):'q0', ('q0','b'):'q1', ('q1','a'):'q0', ('q1','b'):'q1'}
fsm = FSM({'q0','q1'}, {'a','b'}, transitions, 'q0', {'q1'})
fsm.accepts("aab") -> True
fsm.accepts("aba") -> False
```

## Follow-ups

1. How would you convert this DFA to an NFA that accepts the complement language?
2. How do you detect unreachable states and why is removing them useful?
3. How would you implement DFA minimization (merging equivalent states)?
4. What changes are needed to support epsilon transitions (NFA with epsilon)?

States Transitioning: Simulate a Finite State Machine and Detect Reachable States

Question Details

Full Details

Topics

More from Waymo