Class: Stamina::RegLang::CanonicalInfo

Inherits:
Object
  • Object
show all
Defined in:
lib/stamina-induction/stamina/reg_lang/canonical_info.rb

Constant Summary collapse

SHORT_PREFIXES = 
begin
  algo = Stamina::Utils::Decorate.new(:short_prefix)
  algo.set_suppremum do |d0,d1|
    if (d0.nil? || d1.nil?)
      (d0 || d1)
    else
      d0.size <= d1.size ? d0 : d1
    end
  end
  algo.set_propagate do |deco, edge|
    deco.dup << edge.symbol
  end
  algo
end

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(lang) ⇒ CanonicalInfo

Returns a new instance of CanonicalInfo.



22
23
24
 
# File 'lib/stamina-induction/stamina/reg_lang/canonical_info.rb', line 22

def initialize(lang)
  @cdfa = lang.to_cdfa
end

Instance Attribute Details

#cdfa ⇒ Object (readonly)

Returns the value of attribute cdfa.



20
21
22
 
# File 'lib/stamina-induction/stamina/reg_lang/canonical_info.rb', line 20

def cdfa
  @cdfa
end

Instance Method Details

#characteristic_sample ⇒ Object

Builds a characteristic sample



70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
 
# File 'lib/stamina-induction/stamina/reg_lang/canonical_info.rb', line 70

def characteristic_sample
  sample = Sample.new

  # at least one positive string should be found from
  # the initial state
  if pos = positive_suffix(cdfa.initial_state)
    sample << InputString.new(pos, true)
  else
    sample << InputString.new([], false)
    return sample
  end

  # condition 1: positive string for each element of the kernel
  cdfa.each_edge do |edge|
    pos = short_prefix(edge) + positive_suffix(edge.target)
    sample << InputString.new(pos, true, false)
  end

  # condition 2: pair-wise distinguising suffixes
  cdfa.each_state do |source|
    cdfa.each_edge do |edge|
      next if (target = edge.target) == source
      if suffix = distinguish(source, target)
        sign = cdfa.accepts?(suffix, source)
        sample << InputString.new(short_prefix(source) + suffix, sign)
        sample << InputString.new(short_prefix(edge) + suffix, !sign)
      end
    end
  end

  sample
end

#kernel ⇒ Object

Returns the language kernel as a sample



58
59
60
61
62
63
64
65
 
# File 'lib/stamina-induction/stamina/reg_lang/canonical_info.rb', line 58

def kernel
  kernel = Sample.new
  kernel << InputString.new([], cdfa.initial_state.accepting?)
  cdfa.each_edge do |e|
    kernel << InputString.new(short_prefix(e), e.target.accepting?)
  end
  kernel
end

#negative_suffix(state) ⇒ Object

Returns a negative suffix for ‘state`



40
41
42
 
# File 'lib/stamina-induction/stamina/reg_lang/canonical_info.rb', line 40

def negative_suffix(state)
  state[:negative_suffix] ||= find_suffix(state, false)
end

#positive_suffix(state) ⇒ Object

Returns a positive suffix for ‘state`



35
36
37
 
# File 'lib/stamina-induction/stamina/reg_lang/canonical_info.rb', line 35

def positive_suffix(state)
  state[:positive_suffix] ||= find_suffix(state, true)
end

#short_prefix(s_or_e) ⇒ Object

Returns the short prefix of a state or an edge.



27
28
29
30
31
32
 
# File 'lib/stamina-induction/stamina/reg_lang/canonical_info.rb', line 27

def short_prefix(s_or_e)
  prefixes!
  s_or_e[:short_prefix] ||= begin
    s_or_e.source[:short_prefix] + [s_or_e.symbol]
  end
end

#short_prefixes ⇒ Object

Returns the short prefixes of the language as a sample



47
48
49
50
51
52
53
 
# File 'lib/stamina-induction/stamina/reg_lang/canonical_info.rb', line 47

def short_prefixes
  prefixes = Sample.new
  cdfa.each_state do |s|
    prefixes << InputString.new(short_prefix(s), s.accepting?)
  end
  prefixes
end