Java实现一个右线性正规文法的DFA模拟程序

右线性正规文法可以表示为以下形式：

A → aB

A → a

其中A和B是非终结符号，a是终结符号。这个文法可以被转换为DFA，如下所示：

1. 创建一个初始状态S，并将其标记为起始状态和接受状态。

2. 对于每个终结符号a，创建一个状态Sa，将其标记为接受状态。

3. 对于每个非终结符号A，创建一个状态SA，并将其标记为起始状态。

4. 对于每个规则A → aB，将从状态SA到状态SB的转换添加到DFA中。

5. 对于每个规则A → a，将从状态SA到状态Sa的转换添加到DFA中。

下面是这个DFA的Java实现代码：

import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

public class RightLinearGrammarDFA {
    private final Map<String, Map<Character, String>> transitions;
    private final String startState;
    private final String acceptState;

    public RightLinearGrammarDFA() {
        transitions = new HashMap<>();
        startState = "S";
        acceptState = "S";
        transitions.put("S", new HashMap<>());
    }

    public void addRule(String rule) {
        String[] parts = rule.split(" → ");
        String fromState = parts[0];
        String toSymbols = parts[1];

        if (toSymbols.length() == 1) {
            // A → a
            char symbol = toSymbols.charAt(0);
            addTransition(fromState, symbol, "S" + symbol);
        } else {
            // A → aB
            char symbol = toSymbols.charAt(0);
            String nextState = "S" + toSymbols.charAt(1);
            addTransition(fromState, symbol, nextState);
        }
    }

    private void addTransition(String from, char symbol, String to) {
        if (!transitions.containsKey(from)) {
            transitions.put(from, new HashMap<>());
        }
        transitions.get(from).put(symbol, to);
    }

    public boolean accepts(String input) {
        String currentState = startState;
        for (char symbol : input.toCharArray()) {
            if (!transitions.containsKey(currentState) ||
                    !transitions.get(currentState).containsKey(symbol)) {
                return false;
            }
            currentState = transitions.get(currentState).get(symbol);
        }
        return currentState.equals(acceptState);
    }

    public static void main(String[] args) {
        RightLinearGrammarDFA dfa = new RightLinearGrammarDFA();
        Scanner scanner = new Scanner(System.in);
        System.out.print("Enter the number of rules: ");
        int numRules = scanner.nextInt();
        scanner.nextLine(); // consume newline
        System.out.println("Enter the rules in the form A → aB or A → a:");
        for (int i = 0; i < numRules; i++) {
            String rule = scanner.nextLine();
            dfa.addRule(rule);
        }
        System.out.print("Enter a string to test: ");
        String input = scanner.nextLine();
        boolean accepts = dfa.accepts(input);
        System.out.println("The DFA " + (accepts ? "accepts" : "rejects") + " the input.");
    }
}

上面代码中，我们首先定义了一个 `RightLinearGrammarDFA` 类，它包含了转换函数的映射、起始状态和接受状态。在构造函数中，我们创建了起始状态 `S` 并将其标记为起始和接受状态。

`addRule` 方法用于添加规则。如果规则是 `A → a` 的形式，则我们创建一个新状态 `Sa` 并将其标记为接受状态。如果规则是 `A → aB` 的形式，则我们创建一个新状态 `SB` 并将从 `SA` 到 `SB` 的转换添加到DFA中。

`accepts` 方法用于检查输入字符串是否被DFA接受。我们从起始状态开始，遍历输入字符串并使用转换函数将当前状态转换到下一个状态。如果在任何时候我们无法找到下一个状态，则输入被拒绝。如果遍历完整个字符串后我们处于接受状态，则输入被接受。

最后，我们在 `main` 方法中使用 `Scanner` 从控制台读取规则和输入字符串，并使用 `RightLinearGrammarDFA` 类检查输入是否被接受。