Class: Hoozuki::Automaton::NFA

Inherits:
Object
  • Object
show all
Defined in:
lib/hoozuki/automaton/nfa.rb

Instance Attribute Summary collapse

Class Method Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(start, accept) ⇒ NFA

Returns a new instance of NFA.



10
11
12
13
14
 
# File 'lib/hoozuki/automaton/nfa.rb', line 10

def initialize(start, accept)
  @start = start
  @accept = accept
  @transitions = Set.new
end

Instance Attribute Details

#accept ⇒ Object

Returns the value of attribute accept.



8
9
10
 
# File 'lib/hoozuki/automaton/nfa.rb', line 8

def accept
  @accept
end

#start ⇒ Object

Returns the value of attribute start.



8
9
10
 
# File 'lib/hoozuki/automaton/nfa.rb', line 8

def start
  @start
end

#transitions ⇒ Object

Returns the value of attribute transitions.



8
9
10
 
# File 'lib/hoozuki/automaton/nfa.rb', line 8

def transitions
  @transitions
end

Class Method Details

.from_node(node, state) ⇒ Object

Raises:

  • (ArgumentError) 


17
18
19
20
21
 
# File 'lib/hoozuki/automaton/nfa.rb', line 17

def from_node(node, state)
  raise ArgumentError, 'Node cannot be nil' if node.nil?

  node.to_nfa(state)
end

Instance Method Details

#add_epsilon_transition(from, to) ⇒ Object 



42
43
44
 
# File 'lib/hoozuki/automaton/nfa.rb', line 42

def add_epsilon_transition(from, to)
  @transitions << [from, nil, to]
end

#add_transition(from, char, to) ⇒ Object 



46
47
48
 
# File 'lib/hoozuki/automaton/nfa.rb', line 46

def add_transition(from, char, to)
  @transitions << [from, char, to]
end

#epsilon_closure(start_states) ⇒ Object 



24
25
26
27
28
29
30
31
32
33
34
35
36
 
# File 'lib/hoozuki/automaton/nfa.rb', line 24

def epsilon_closure(start_states)
  visited = start_states.dup
  queue = start_states.to_a

  while (current = queue.shift)
    destinations = @transitions.select { |from, label, _| from == current && label.nil? }.map(&:last)
    destinations.each do |dest|
      queue << dest if visited.add?(dest)
    end
  end

  Set.new(visited)
end

#merge_transitions(other) ⇒ Object 



38
39
40
 
# File 'lib/hoozuki/automaton/nfa.rb', line 38

def merge_transitions(other)
  @transitions.merge(other.transitions)
end