java 有穷自动机_python实现DFA模拟程序(附java实现代码)

以下是Python实现DFA的示例代码：

class DFA:
    def __init__(self, alphabet, states, start_state, accept_states, transitions):
        self.alphabet = alphabet
        self.states = states
        self.start_state = start_state
        self.accept_states = accept_states
        self.transitions = transitions

    def run(self, input_string):
        current_state = self.start_state
        for char in input_string:
            if char not in self.alphabet:
                return False
            current_state = self.transitions[current_state][char]
        return current_state in self.accept_states

# 示例用法
alphabet = {'0', '1'}
states = {'q0', 'q1', 'q2'}
start_state = 'q0'
accept_states = {'q2'}
transitions = {
    'q0': {'0': 'q1', '1': 'q0'},
    'q1': {'0': 'q2', '1': 'q0'},
    'q2': {'0': 'q2', '1': 'q2'}
}
dfa = DFA(alphabet, states, start_state, accept_states, transitions)
print(dfa.run('1010'))  # 输出 True

以下是Java实现DFA的示例代码：

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

public class DFA {
    private final Set<Character> alphabet;
    private final Set<String> states;
    private final String startState;
    private final Set<String> acceptStates;
    private final Map<String, Map<Character, String>> transitions;

    public DFA(Set<Character> alphabet, Set<String> states, String startState, Set<String> acceptStates, Map<String, Map<Character, String>> transitions) {
        this.alphabet = alphabet;
        this.states = states;
        this.startState = startState;
        this.acceptStates = acceptStates;
        this.transitions = transitions;
    }

    public boolean run(String inputString) {
        String currentState = startState;
        for (char c : inputString.toCharArray()) {
            if (!alphabet.contains(c)) {
                return false;
            }
            currentState = transitions.get(currentState).get(c);
        }
        return acceptStates.contains(currentState);
    }

    // 示例用法
    public static void main(String[] args) {
        Set<Character> alphabet = new HashSet<>();
        alphabet.add('0');
        alphabet.add('1');

        Set<String> states = new HashSet<>();
        states.add("q0");
        states.add("q1");
        states.add("q2");

        String startState = "q0";

        Set<String> acceptStates = new HashSet<>();
        acceptStates.add("q2");

        Map<String, Map<Character, String>> transitions = new HashMap<>();
        Map<Character, String> q0Transitions = new HashMap<>();
        q0Transitions.put('0', "q1");
        q0Transitions.put('1', "q0");
        transitions.put("q0", q0Transitions);

        Map<Character, String> q1Transitions = new HashMap<>();
        q1Transitions.put('0', "q2");
        q1Transitions.put('1', "q0");
        transitions.put("q1", q1Transitions);

        Map<Character, String> q2Transitions = new HashMap<>();
        q2Transitions.put('0', "q2");
        q2Transitions.put('1', "q2");
        transitions.put("q2", q2Transitions);

        DFA dfa = new DFA(alphabet, states, startState, acceptStates, transitions);
        System.out.println(dfa.run("1010")); // 输出 true
    }
}