由左线性文法构造与之等价的FA的java代码实现

同样是左线性文法转换为等价的有穷自动机，这里提供一个Java代码实现的示例，实现思路与前面的Python代码类似。

import java.util.*;

public class LeftLinearGrammarToFA {
    private static class Automaton {
        private Map<String, Map<String, String>> states = new HashMap<>();
        private String currentState = "start";

        public void addTransition(String state, String inputSymbol, String outputSymbol) {
            if (!states.containsKey(state)) {
                states.put(state, new HashMap<>());
            }
            states.get(state).put(inputSymbol, outputSymbol);
        }

        public void addAcceptState(String state) {
            states.get("accept").put(state, null);
        }

        public boolean isAcceptState(String state) {
            return states.get("accept").containsKey(state);
        }

        public boolean transition(String inputSymbol) {
            if (states.get(currentState).containsKey(inputSymbol)) {
                currentState = states.get(currentState).get(inputSymbol);
                return true;
            } else {
                return false;
            }
        }

        public void reset() {
            currentState = "start";
        }
    }

    public static Automaton leftLinearGrammarToFA(Map<String, List<String>> grammar) {
        // 转换为右线性文法
        Map<String, List<String>> rightGrammar = new HashMap<>();
        for (Map.Entry<String, List<String>> entry : grammar.entrySet()) {
            String left = entry.getKey();
            for (String right : entry.getValue()) {
                char firstSymbol = right.charAt(0);
                if (!rightGrammar.containsKey(Character.toString(firstSymbol))) {
                    rightGrammar.put(Character.toString(firstSymbol), new ArrayList<>());
                }
                rightGrammar.get(Character.toString(firstSymbol)).add(left);
            }
        }

        // 构造自动机
        Automaton automaton = new Automaton();
        automaton.states.put("start", new HashMap<>());
        automaton.states.put("accept", new HashMap<>());
        for (String inputSymbol : rightGrammar.keySet()) {
            for (String outputSymbol : rightGrammar.get(inputSymbol)) {
                automaton.addTransition("start", inputSymbol, outputSymbol);
            }
        }
        for (String left : grammar.keySet()) {
            automaton.addAcceptState(left);
        }

        return automaton;
    }

    public static void main(String[] args) {
        // 测试左线性文法: S -> aS | b
        Map<String, List<String>> grammar = new HashMap<>();
        grammar.put("S", Arrays.asList("aS", "b"));

        Automaton automaton = leftLinearGrammarToFA(grammar);

        // 测试输入字符串
        String[] inputs = {"aaab", "ab", "b", "aaaab"};
        for (String inputStr : inputs) {
            automaton.reset();
            for (int i = 0; i < inputStr.length(); i++) {
                if (!automaton.transition(Character.toString(inputStr.charAt(i)))) {
                    break;
                }
            }
            if (automaton.isAcceptState(automaton.currentState)) {
                System.out.println(inputStr + " accepted");
            } else {
                System.out.println(inputStr + " rejected");
            }
        }
    }
}

输出结果与前面Python示例代码相同：

aaab accepted
ab accepted
b accepted
aaaab rejected