Method: Kleene::NFA#reachable_states

Defined in:
lib/kleene/nfa.rb

#reachable_states(start_state) ⇒ Object

Returns a set of State objects which are reachable through any transition path from the NFA’s start_state.



216
217
218
219
220
221
222
223
224
225
226
 
# File 'lib/kleene/nfa.rb', line 216

def reachable_states(start_state)
  visited_states = Set.new()
  unvisited_states = Set[start_state]
  while !unvisited_states.empty?
    outbound_transitions = unvisited_states.flat_map {|state| @transitions[state]&.values&.flat_map(&:to_a) || Array.new }
    destination_states = outbound_transitions.map(&:to).to_set
    visited_states.merge(unvisited_states)         # add the unvisited states to the visited_states
    unvisited_states = destination_states - visited_states
  end
  visited_states
end