Class: Kleene::MultiMatchDFA

Inherits:
Object
  • Object
show all
Includes:
DSL
Defined in:
lib/kleene/multi_match_dfa.rb

Direct Known Subclasses

BatchMultiMatchDFA

Instance Attribute Summary collapse

Instance Method Summary collapse

Methods included from DSL

#any, #append, #append!, #dot, #kleene, #literal, #optional, #plus, #range, #seq, #seq2, #union, #union!, #with_err, #with_err!, #with_err_dead_end, #with_err_dead_end!

Constructor Details

#initialize(nfas) ⇒ MultiMatchDFA

Returns a new instance of MultiMatchDFA.



28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
 
# File 'lib/kleene/multi_match_dfa.rb', line 28

def initialize(nfas)
  composite_alphabet = nfas.reduce(Set.new) {|memo, nfa| memo | nfa.alphabet }

  @original_nfas = nfas
  @nfas_with_err_state = nfas.map {|nfa| with_err_dead_end(nfa, composite_alphabet) }     # copy NFAs and add dead-end error states to each of them
  dfas = @original_nfas.map(&:to_dfa)

  @nfa_to_index = @original_nfas.map.with_index {|nfa, index| [nfa, index] }.to_h
  @nfa_with_dead_err_to_index = @nfas_with_err_state.map.with_index {|nfa, index| [nfa, index] }.to_h
  @dfa_to_index = dfas.map.with_index {|dfa, index| [dfa, index] }.to_h
  @machines_by_index = @original_nfas.zip(nfas_with_err_state, dfas).map.with_index {|tuple, index| nfa, nfa_with_dead_err, dfa = tuple; [index, MachineTuple.new(nfa, nfa_with_dead_err, dfa)] }.to_h

  # build a mapping of (state -> nfa) pairs that capture which nfa owns each state
  @dead_end_nfa_state_to_dead_end_nfa = Hash.new
  @nfas_with_err_state.each do |nfa_with_dead_err|
    nfa_with_dead_err.states.each do |state|
      @dead_end_nfa_state_to_dead_end_nfa[state] = nfa_with_dead_err
    end
  end

  # create a composite NFA as the union of all the NFAs with epsilon transitions from every NFA state back to the union NFA's start state
  @composite_nfa = create_composite_nfa(@nfas_with_err_state)
  @composite_dfa = @composite_nfa.to_dfa
end

Instance Attribute Details

#composite_dfa ⇒ Object

: DFA



21
22
23
 
# File 'lib/kleene/multi_match_dfa.rb', line 21

def composite_dfa
  @composite_dfa
end

#composite_nfa ⇒ Object

: NFA



20
21
22
 
# File 'lib/kleene/multi_match_dfa.rb', line 20

def composite_nfa
  @composite_nfa
end

#dead_end_nfa_state_to_dead_end_nfa ⇒ Object

: Hash(State, NFA)



19
20
21
 
# File 'lib/kleene/multi_match_dfa.rb', line 19

def dead_end_nfa_state_to_dead_end_nfa
  @dead_end_nfa_state_to_dead_end_nfa
end

#dfa_to_index ⇒ Object

: Hash(DFA, Int32)



26
27
28
 
# File 'lib/kleene/multi_match_dfa.rb', line 26

def dfa_to_index
  @dfa_to_index
end

#machines_by_index ⇒ Object

: Hash(Int32, MachineTuple)



23
24
25
 
# File 'lib/kleene/multi_match_dfa.rb', line 23

def machines_by_index
  @machines_by_index
end

#nfa_to_index ⇒ Object

: Hash(NFA, Int32)



24
25
26
 
# File 'lib/kleene/multi_match_dfa.rb', line 24

def nfa_to_index
  @nfa_to_index
end

#nfa_with_dead_err_to_index ⇒ Object

: Hash(NFA, Int32)



25
26
27
 
# File 'lib/kleene/multi_match_dfa.rb', line 25

def nfa_with_dead_err_to_index
  @nfa_with_dead_err_to_index
end

#nfas_with_err_state ⇒ Object (readonly)

Returns the value of attribute nfas_with_err_state.



18
19
20
 
# File 'lib/kleene/multi_match_dfa.rb', line 18

def nfas_with_err_state
  @nfas_with_err_state
end

Instance Method Details

#create_composite_nfa(nfas) ⇒ Object

create a composite NFA as the union of all the NFAs with epsilon transitions from every NFA state back to the union NFA’s start state



66
67
68
69
70
71
72
73
74
75
76
77
78
79
 
# File 'lib/kleene/multi_match_dfa.rb', line 66

def create_composite_nfa(nfas)
  nfa = union!(nfas)

  # add epsilon transitions from all the states except the start state back to the start state
  nfa.states.each do |state|
    if state != nfa.start_state
      nfa.add_transition(NFATransition::Epsilon, state, nfa.start_state)
    end
  end

  nfa.update_final_states

  nfa
end

#machines_from_dfa(dfa) ⇒ Object

: MachineTuple



61
62
63
 
# File 'lib/kleene/multi_match_dfa.rb', line 61

def machines_from_dfa(dfa) # : MachineTuple
  machines_by_index[dfa_to_index[dfa]]
end

#machines_from_nfa(nfa) ⇒ Object

: MachineTuple



53
54
55
 
# File 'lib/kleene/multi_match_dfa.rb', line 53

def machines_from_nfa(nfa) # : MachineTuple
  machines_by_index[nfa_to_index[nfa]]
end

#machines_from_nfa_with_dead_err(nfa_with_dead_err) ⇒ Object

: MachineTuple



57
58
59
 
# File 'lib/kleene/multi_match_dfa.rb', line 57

def machines_from_nfa_with_dead_err(nfa_with_dead_err) # : MachineTuple
  machines_by_index[nfa_with_dead_err_to_index[nfa_with_dead_err]]
end