Понимание алгоритма закрытия epsilon pseudocode

Question

Следующий псевдокод от Введение в построение компилятора в мире Java книга. Предполагается, что этот алгоритм выводит epsilon-замыкание множества состояний недетерминированной конечной машины (в конечном итоге преобразует ее в детерминированную).

# Input: a set of states, S 
# Output: epsilon_closure(S) 

    Stack P.addAll(S) #a stack containing all states in S 
    Set C.addAll(S) #the closure initially contains the states in S 

    while ! P.empty() do 
     s = P.pop() 
     for r in m(s, epsilon) do 
      # m(s, epsilon) is a set of states 
      if r not in C then 
       P.push(r) 
       C.add(r) 
      end if 
     end for 

    end while 
    return C 

Я знаю, что такое закрытие epsilon, но, к сожалению, мне трудно понять, как работает этот код.

Примечание: m() в коде является функцией перехода на станцию.

Answer 1

Он просто применяет функцию перехода к каждому состоянию в S. Состояния, полученные в результате этого приложения, собираются в C. После того, как вы закончите просмотр каждого состояния в P, C содержит закрытие epsilon.

Обратите внимание, что вход S не обязательно является полным набором состояний в NFA, так что пересечение S и m (s, epsilon) может быть пустым.