Simulate a Deterministic Finite Automaton

Problem Statement

A Deterministic Finite Automaton (DFA) is a finite-state machine that accepts or rejects a given string of symbols by stepping through a sequence of states according to a fixed transition function.

Implement a class DFASimulator that represents a DFA over the alphabet {"a", "b"} and determines whether given input strings are accepted.

The DFA is defined formally by a 5-tuple (Q, Sigma, delta, q0, F):

• Q: A finite set of states (represented as strings).
• Sigma: The alphabet, restricted here to {"a", "b"}.
• delta: A transition function mapping a pair of (current_state, symbol) to a next_state.
• q0: The start state (q0 must be in Q).
• F: A set of accept/final states (F is a subset of Q).

Implement the following methods in DFASimulator:

1. __init__(self, states: list[str], transitions: dict[str, dict[str, str]], start_state: str, accept_states: list[str]):

   • Initializes the automaton. transitions[u][char] gives the state reached from state u on reading char.
   • If a transition is missing for a state and character pair, treat that transition as entering an implicit permanent reject state (sink state).

2. accepts(self, s: str) -> bool:

   • Processes the string s symbol by symbol starting from start_state.
   • Returns True if the machine ends in a state in accept_states after consuming all characters of s, and False otherwise.
   • If s contains characters not in {"a", "b"}, or if the machine encounters a missing transition, the string must be rejected.
   • An empty string "" consumes 0 characters and is accepted if and only if start_state is in accept_states.

Examples

Example 1

A DFA that accepts any string ending in "ab":

states = ["q0", "q1", "q2"]
transitions = {
    "q0": {"a": "q1", "b": "q0"},
    "q1": {"a": "q1", "b": "q2"},
    "q2": {"a": "q1", "b": "q0"}
}
start_state = "q0"
accept_states = ["q2"]

dfa = DFASimulator(states, transitions, start_state, accept_states)

print(dfa.accepts("aab"))   # Output: True
print(dfa.accepts("ab"))    # Output: True
print(dfa.accepts("aba"))   # Output: False
print(dfa.accepts(""))      # Output: False

Example 2

A DFA with an accepting start state (accepts strings with an even number of 'a's):

states = ["even", "odd"]
transitions = {
    "even": {"a": "odd", "b": "even"},
    "odd":  {"a": "even", "b": "odd"}
}
start_state = "even"
accept_states = ["even"]

dfa = DFASimulator(states, transitions, start_state, accept_states)

print(dfa.accepts(""))      # Output: True (0 'a's is even)
print(dfa.accepts("b"))     # Output: True
print(dfa.accepts("ba"))    # Output: False
print(dfa.accepts("baab"))  # Output: True

Constraints

• 1 <= len(states) <= 10^4
• 0 <= len(accept_states) <= len(states)
• 0 <= len(s) <= 10^5 for each query to accepts
• Number of calls to accepts <= 100
• Characters in s are printable ASCII characters.
• accepts(s) must run in O(len(s)) time and O(1) auxiliary space.