Untitled

import java.util.*;

public class NFA {
    private int statesCount;
    private Set<Integer> finalStates;
    private Map<Character, List<Integer>>[] transitions;

    public NFA(String regex) {
        finalStates = new HashSet<>();
        // Построение НКА по регулярному выражению
        // ...
    }

    // Добавление перехода
    private void addTransition(int state, char symbol, int nextState) {
        if (transitions[state] == null) {
            transitions[state] = new HashMap<>();
        }
        if (!transitions[state].containsKey(symbol)) {
            transitions[state].put(symbol, new ArrayList<>());
        }
        transitions[state].get(symbol).add(nextState);
    }

    // Получение множества состояний, достижимых из данного множества по символу
    private Set<Integer> move(Set<Integer> states, char symbol) {
        Set<Integer> nextStates = new HashSet<>();
        for (int state : states) {
            if (transitions[state] != null && transitions[state].containsKey(symbol)) {
                nextStates.addAll(transitions[state].get(symbol));
            }
        }
        return nextStates;
    }

    // Получение множества состояний, достижимых из данного множества по эпсилон-переходу
    private Set<Integer> epsilonClosure(Set<Integer> states) {
        Set<Integer> closure = new HashSet<>(states);
        Queue<Integer> queue = new LinkedList<>(states);
        while (!queue.isEmpty()) {
            int state = queue.poll();
            if (transitions[state] != null && transitions[state].containsKey(null)) {
                for (int nextState : transitions[state].get(null)) {
                    if (!closure.contains(nextState)) {
                        closure.add(nextState);
                        queue.offer(nextState);
                    }
                }
            }
        }
        return closure;
    }

    // Проверка, принадлежит ли данная строка языку, задаваемому НКА
    public boolean accepts(String str) {
        Set<Integer> currentStates = epsilonClosure(Collections.singleton(0));
        for (char symbol : str.toCharArray()) {
            currentStates = epsilonClosure(move(currentStates, symbol));
        }
        return !Collections.disjoint(currentStates, finalStates);
    }
}