Class: Resyma::Core::Automaton

Inherits:
Object
  • Object
show all
Defined in:
lib/resyma/core/automaton/definition.rb,
lib/resyma/core/automaton/epsilon_NFA.rb,
lib/resyma/core/automaton/visualize.rb

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(start, accept_set, transition_table = TransitionTable.new) ⇒ Automaton

Returns a new instance of Resyma::Core::Automaton

Parameters:



15
16
17
18
19
 
# File 'lib/resyma/core/automaton/definition.rb', line 15

def initialize(start, accept_set, transition_table = TransitionTable.new)
  @start = start
  @accept_set = accept_set
  @transition_table = transition_table
end

Instance Attribute Details

#accept_set ⇒ Object (readonly)

Returns the value of attribute accept_set.



21
22
23
 
# File 'lib/resyma/core/automaton/definition.rb', line 21

def accept_set
  @accept_set
end

#start ⇒ Object (readonly)

Returns the value of attribute start.



21
22
23
 
# File 'lib/resyma/core/automaton/definition.rb', line 21

def start
  @start
end

#transition_table ⇒ Object (readonly)

Returns the value of attribute transition_table.



21
22
23
 
# File 'lib/resyma/core/automaton/definition.rb', line 21

def transition_table
  @transition_table
end

Instance Method Details

#accept?(state) ⇒ Boolean

Returns:

  • (Boolean) 


23
24
25
 
# File 'lib/resyma/core/automaton/definition.rb', line 23

def accept?(state)
  @accept_set.include? state
end

#destination(state, value) ⇒ Object 



27
28
29
 
# File 'lib/resyma/core/automaton/definition.rb', line 27

def destination(state, value)
  @transition_table.destination(state, value)
end

#eclose(state_set) ⇒ Set<Resyma::Core::State>

Computes the epsilon-closure of ‘state`

Parameters:

Returns:



22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
 
# File 'lib/resyma/core/automaton/epsilon_NFA.rb', line 22

def eclose(state_set)
  queue = state_set.to_a
  closure = queue.to_set
  until queue.empty?
    next_state = queue.shift
    transition_table.candidates(next_state).each do |can|
      next unless can.condition.equal?(Epsilon) &&
                  !closure.include?(can.destination)

      closure.add(can.destination)
      queue.push(can.destination)
    end
  end
  closure
end

#generate_reachable_epsilon_closures(epsilon_closure, closure_map, ab) ⇒ Array<Set>

Computes next epsilon-closures connecting with ‘epsilon_closure`

Parameters:

Returns:

  • (Array<Set>) —

    New unrecorded epsilon-closures



55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
 
# File 'lib/resyma/core/automaton/epsilon_NFA.rb', line 55

def generate_reachable_epsilon_closures(epsilon_closure, closure_map, ab)
  current_state = closure_map[epsilon_closure]
  condition_sets = epsilon_closure.map do |state|
    possible_nonepsilon_conditions(state)
  end
  new_closures = []
  Utils.big_union(condition_sets).each do |cond|
    new_closure = Set[]
    epsilon_closure.each do |state|
      # [WARN] We are using a `matchable` as a `matched value, which may
      # cause unexpected consequence
      dst = destination(state, cond)
      new_closure.add dst unless dst.nil?
    end
    raise "Internal error: No destination states" if new_closure.empty?

    new_closure = eclose(new_closure)
    if closure_map.include?(new_closure)
      recorded_state = closure_map[new_closure]
      ab.add_transition!(current_state, cond, recorded_state)
    else
      new_state = ab.new_state!
      closure_map[new_closure] = new_state
      ab.add_transition!(current_state, cond, new_state)
      new_closures.push new_closure
    end
  end
  new_closures
end

#has_epsilon? ⇒ Boolean

Returns:

  • (Boolean) 


105
106
107
108
109
110
111
112
 
# File 'lib/resyma/core/automaton/epsilon_NFA.rb', line 105

def has_epsilon?
  transition_table.table.values.each do |cans|
    cans.each do |can|
      return true if can.condition.equal?(Epsilon)
    end
  end
  false
end

#possible_nonepsilon_conditions(state) ⇒ Object 



38
39
40
41
42
 
# File 'lib/resyma/core/automaton/epsilon_NFA.rb', line 38

def possible_nonepsilon_conditions(state)
  transition_table.candidates(state).map(&:condition).select do |cond|
    !cond.equal?(Epsilon)
  end.to_set
end

#to_DFA ⇒ Object 



85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
 
# File 'lib/resyma/core/automaton/epsilon_NFA.rb', line 85

def to_DFA
  ab = AutomatonBuilder.new
  start_closure = eclose(Set[start])
  start_state = ab.new_state!
  ab.start! start_state
  closure_map = { start_closure => start_state }
  queue = [start_closure]
  until queue.empty?
    next_closure = queue.shift
    unrecorded_closures = generate_reachable_epsilon_closures(
      next_closure, closure_map, ab
    )
    queue += unrecorded_closures
  end
  closure_map.each do |closure, state|
    ab.accept! state if closure.any? { |s| accept? s }
  end
  ab.build
end

#to_lwg(port = $>) ⇒ Object 



8
9
10
11
12
13
14
15
16
17
18
19
20
 
# File 'lib/resyma/core/automaton/visualize.rb', line 8

def to_lwg(port = $>)
  transition_table.table.each do |state, candidates|
    candidates.each do |can|
      port << "#{state.id} - #{can.destination.id}\n"
      port <<
        %(move.#{state.id}.#{can.destination.id} = "#{can.condition}"\n)
    end
  end
  accept_set.each do |state|
    port << "accept.#{state.id}\n"
  end
  port << "start.from.#{start.id}\n"
end