Class: Hoozuki::Automaton::DFA

Inherits:
Object
  • Object
show all
Defined in:
lib/hoozuki/automaton/dfa.rb,
lib/hoozuki/automaton/dfa/builder.rb

Defined Under Namespace

Classes: Builder

Instance Attribute Summary collapse

Class Method Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(start, accept) ⇒ DFA

Returns a new instance of DFA.



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

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

Instance Attribute Details

#accept ⇒ Object (readonly)

Returns the value of attribute accept.



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

def accept
  @accept
end

#start ⇒ Object (readonly)

Returns the value of attribute start.



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

def start
  @start
end

#transitions ⇒ Object (readonly)

Returns the value of attribute transitions.



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

def transitions
  @transitions
end

Class Method Details

.from_nfa(nfa, use_cache) ⇒ Object 



18
19
20
 
# File 'lib/hoozuki/automaton/dfa.rb', line 18

def from_nfa(nfa, use_cache)
  Builder.new(nfa, use_cache).call
end

Instance Method Details

#match?(input, use_cache) ⇒ Boolean

Returns:

  • (Boolean) 


31
32
33
34
35
36
37
38
39
40
41
42
 
# File 'lib/hoozuki/automaton/dfa.rb', line 31

def match?(input, use_cache)
  state = @start

  input.each_char do |char|
    next_state = next_transition(state, char, use_cache)
    return false unless next_state

    state = next_state
  end

  @accept.include?(state)
end

#next_transition(current, input, use_cache) ⇒ Object 



23
24
25
26
27
28
29
 
# File 'lib/hoozuki/automaton/dfa.rb', line 23

def next_transition(current, input, use_cache)
  if use_cache && (next_state = @cache[[current, input]])
    return next_state
  end

  @transitions.find { |from, label, _| from == current && label == input }&.last
end