Class: Stamina::RegLang

Inherits:
Object
  • Object
show all
Defined in:
lib/stamina-induction/stamina/reg_lang.rb,
lib/stamina-induction/stamina/reg_lang/parser/node.rb,
lib/stamina-induction/stamina/reg_lang/parser/plus.rb,
lib/stamina-induction/stamina/reg_lang/parser/star.rb,
lib/stamina-induction/stamina/reg_lang/parser/regexp.rb,
lib/stamina-induction/stamina/reg_lang/parser/symbol.rb,
lib/stamina-induction/stamina/reg_lang/canonical_info.rb,
lib/stamina-induction/stamina/reg_lang/parser/question.rb,
lib/stamina-induction/stamina/reg_lang/parser/sequence.rb,
lib/stamina-induction/stamina/reg_lang/parser/alternative.rb,
lib/stamina-induction/stamina/reg_lang/parser/parenthesized.rb

Defined Under Namespace

Modules: Alternative, Node, Parenthesized, Plus, Question, Regexp, Sequence, Star, Symbol Classes: CanonicalInfo

Constant Summary collapse

EMPTY = 
RegLang.new(Automaton::DUM)

Class Method Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(fa) ⇒ RegLang

Creates a regular language instance based on an automaton.



12
13
14
 
# File 'lib/stamina-induction/stamina/reg_lang.rb', line 12

def initialize(fa)
  @fa = fa
end

Class Method Details

.coerce(arg) ⇒ Object

Coerces ‘arg` to a regular language

Raises:

  • ArgumentError if ‘arg` cannot be coerced to a regular language



24
25
26
27
28
29
30
31
32
33
34
 
# File 'lib/stamina-induction/stamina/reg_lang.rb', line 24

def self.coerce(arg)
  if arg.respond_to?(:to_reglang)
    arg.to_reglang
  elsif arg.respond_to?(:to_fa)
    new(arg.to_fa)
  elsif arg.is_a?(String)
    parse(arg)
  else
    raise ArgumentError, "Invalid argument #{arg} for `RegLang`"
  end
end

.parse(str) ⇒ Object

Creates a regular language by parsing an expression.



52
53
54
 
# File 'lib/stamina-induction/stamina/reg_lang.rb', line 52

def self.parse(str)
  RegLang.new(Parser.parse(str).to_fa)
end

.sigma_star(alph) ⇒ Object

Builds a sigma star language



39
40
41
42
43
44
45
46
47
 
# File 'lib/stamina-induction/stamina/reg_lang.rb', line 39

def self.sigma_star(alph)
  new(Automaton.new do |fa|
    fa.alphabet = alph.to_a
    fa.add_state(:initial => true, :accepting => true)
    alph.each do |symbol|
      fa.connect(0,0,symbol)
    end
  end)
end

Instance Method Details

#*(other) ⇒ Object Also known as: &, intersection

Returns a regular language defined as the intersection of ‘self` with `other`.



96
97
98
 
# File 'lib/stamina-induction/stamina/reg_lang.rb', line 96

def *(other)
  RegLang.new(fa.compose(other.fa))
end

#**(x) ⇒ Object

Raises:

  • (ArgumentError) 


75
76
77
78
 
# File 'lib/stamina-induction/stamina/reg_lang.rb', line 75

def **(x)
  raise ArgumentError, "Invalid argument for ** (#{x})" unless x == -1
  complement
end

#+(other) ⇒ Object Also known as: |, union

Returns a regular language defined as the union of ‘self` with `other`.



83
84
85
86
87
88
 
# File 'lib/stamina-induction/stamina/reg_lang.rb', line 83

def +(other)
  unioned = Automaton.new
  fa.dup(unioned)
  other.to_fa.dup(unioned)
  RegLang.new(unioned)
end

#-(other) ⇒ Object Also known as: difference

Returns a regular language defined capturing all strings from ‘self` but those in common with `other`.



106
107
108
 
# File 'lib/stamina-induction/stamina/reg_lang.rb', line 106

def -(other)
  self & other.complement
end

#characteristic_sample ⇒ Object 



136
137
138
 
# File 'lib/stamina-induction/stamina/reg_lang.rb', line 136

def characteristic_sample
  canonical_info.characteristic_sample
end

#complement ⇒ Object

Returns the complement of this regular language



71
72
73
 
# File 'lib/stamina-induction/stamina/reg_lang.rb', line 71

def complement
  RegLang.new(to_dfa.complement)
end

#empty? ⇒ Boolean

Checks if the language is empty

Returns:

  • (Boolean) 


153
154
155
 
# File 'lib/stamina-induction/stamina/reg_lang.rb', line 153

def empty?
  self <=> EMPTY
end

#eql?(other) ⇒ Boolean Also known as: <=>

Checks if ‘self` and `other` capture the same regular language.

Returns:

  • (Boolean) 


167
168
169
 
# File 'lib/stamina-induction/stamina/reg_lang.rb', line 167

def eql?(other)
  self.to_cdfa <=> other.to_cdfa
end

#hide(symbols) ⇒ Object

Returns the regular language defined when abstracting from ‘symbols`



114
115
116
 
# File 'lib/stamina-induction/stamina/reg_lang.rb', line 114

def hide(symbols)
  RegLang.new(fa.hide(symbols))
end

#include?(str) ⇒ Boolean

Checks if this regular language includes a given string

Returns:

  • (Boolean) 


160
161
162
 
# File 'lib/stamina-induction/stamina/reg_lang.rb', line 160

def include?(str)
  fa.accepts?(str)
end

#kernel ⇒ Object 



132
133
134
 
# File 'lib/stamina-induction/stamina/reg_lang.rb', line 132

def kernel
  canonical_info.kernel
end

#prefix_closed ⇒ Object

Returns the prefix-closed version of this regular language.



62
63
64
65
66
 
# File 'lib/stamina-induction/stamina/reg_lang.rb', line 62

def prefix_closed
  automaton = fa.dup
  automaton.each_state{|s| s.accepting!}
  RegLang.new(automaton)
end

#project(symbols) ⇒ Object

Returns the regular language defined when projecting on ‘symbols`



121
122
123
 
# File 'lib/stamina-induction/stamina/reg_lang.rb', line 121

def project(symbols)
  RegLang.new(fa.keep(symbols))
end

#short_prefixes ⇒ Object

CANONICAL DFA



128
129
130
 
# File 'lib/stamina-induction/stamina/reg_lang.rb', line 128

def short_prefixes
  canonical_info.short_prefixes
end

#to_adl ⇒ Object 



219
220
221
 
# File 'lib/stamina-induction/stamina/reg_lang.rb', line 219

def to_adl
  to_cdfa.to_adl
end

#to_cdfa ⇒ Object

Returns the canonical deterministic finite automaton capturing this regular language.



205
206
207
 
# File 'lib/stamina-induction/stamina/reg_lang.rb', line 205

def to_cdfa
  fa.to_cdfa
end

#to_dfa ⇒ Object

Returns a deterministic finite automaton capturing this regular language.

Returned automaton is not guaranteed to be minimal or canonical.



197
198
199
 
# File 'lib/stamina-induction/stamina/reg_lang.rb', line 197

def to_dfa
  fa.determinize
end

#to_dot ⇒ Object

Returns a dot output



212
213
214
215
216
217
 
# File 'lib/stamina-induction/stamina/reg_lang.rb', line 212

def to_dot
  dfa = to_cdfa
  dfa.depth
  dfa.order_states{|s,t| s[:depth] <=> t[:depth]}
  dfa.to_dot
end

#to_fa ⇒ Object

Returns a finite automaton capturing this regular language.

Returned automaton may be non-deterministic.



187
188
189
 
# File 'lib/stamina-induction/stamina/reg_lang.rb', line 187

def to_fa
  fa.dup
end

#to_reglang ⇒ Object

Returns self.



178
179
180
 
# File 'lib/stamina-induction/stamina/reg_lang.rb', line 178

def to_reglang
  self
end