Class: Stamina::Automaton::State

Inherits:
Object
  • Object
show all
Includes:
Markable
Defined in:
lib/stamina-core/stamina/automaton/state.rb

Overview

Automaton state.

Instance Attribute Summary collapse

Instance Method Summary collapse

Methods included from Markable

#[], #[]=, #data, #marks, #raw_data, #remove_mark

Constructor Details

#initialize(automaton, index, data) ⇒ State

Creates a state.

Arguments:

  • automaton: parent automaton of the state.

  • index: index of the state in the state list.

  • data: user data attached to this state.



18
19
20
21
22
23
24
25
 
# File 'lib/stamina-core/stamina/automaton/state.rb', line 18

def initialize(automaton, index, data)
  @automaton = automaton
  @index = index
  @data = data.dup
  @out_edges = []
  @in_edges = []
  @epsilon_closure = nil
end

Instance Attribute Details

#automaton ⇒ Object (readonly)

Returns the value of attribute automaton.



8
9
10
 
# File 'lib/stamina-core/stamina/automaton/state.rb', line 8

def automaton
  @automaton
end

#index ⇒ Object

Returns the value of attribute index.



8
9
10
 
# File 'lib/stamina-core/stamina/automaton/state.rb', line 8

def index
  @index
end

Instance Method Details

#<=>(o) ⇒ Object

Provides comparator of states, based on the index in the automaton state list. This method returns nil unless o is a State from the same automaton than self.



208
209
210
211
212
 
# File 'lib/stamina-core/stamina/automaton/state.rb', line 208

def <=>(o)
  return nil unless State===o
  return nil unless automaton===o.automaton
  return index <=> o.index
end

#accepting!(value = true) ⇒ Object

Sets this state as an accepting state.



46
47
48
 
# File 'lib/stamina-core/stamina/automaton/state.rb', line 46

def accepting!(value = true)
  @data[:accepting] = value
end

#accepting? ⇒ Boolean

Returns true if this state is an accepting state, false otherwise.

Returns:

  • (Boolean) 


41
42
43
 
# File 'lib/stamina-core/stamina/automaton/state.rb', line 41

def accepting?
  !!@data[:accepting]
end

#adjacent_states ⇒ Object

Returns an array with adjacent states (in or out edge).

Returned array may be modified.



114
115
116
 
# File 'lib/stamina-core/stamina/automaton/state.rb', line 114

def adjacent_states()
  (in_adjacent_states+out_adjacent_states).uniq
end

#delta(symbol) ⇒ Object

Computes an array representing the set of states that can be reached from this state with a given input symbol. Returned array does not contain duplicates and may be modified. No particular ordering of states in the array is guaranteed.

This method is epsilon symbol aware (represented with nil) on non deterministic automata, meaning that it actually computes the set of reachable states through strings respecting the eps* symbol eps* regular expression, where eps is the epsilon symbol.



180
181
182
183
184
185
186
187
188
189
 
# File 'lib/stamina-core/stamina/automaton/state.rb', line 180

def delta(symbol)
  if automaton.deterministic?
    target = dfa_delta(symbol)
    target.nil? ? [] : [target]
  else
    at_epsilon = epsilon_closure
    at_espilon_then_symbol = at_epsilon.map{|s| s.step(symbol)}.flatten.uniq
    at_espilon_then_symbol.map{|s| s.epsilon_closure}.flatten.uniq
  end
end

#deterministic? ⇒ Boolean

Returns true if this state is deterministic, false otherwise.

Returns:

  • (Boolean) 


61
62
63
64
 
# File 'lib/stamina-core/stamina/automaton/state.rb', line 61

def deterministic?
  outs = out_symbols
  (outs.size==@out_edges.size) and not(outs.include?(nil))
end

#dfa_delta(symbol) ⇒ Object

Returns the target state that can be reached from this state with symbol input. Returns nil if no such state exists.

This method is expected to be used on deterministic automata. Unlike delta, it returns a State instance (or nil), not an array of states. When used on non deterministic automata, it returns a state immediately reachable from this state with symbol input, or nil if no such state exists. This method is not epsilon aware.



199
200
201
202
203
 
# File 'lib/stamina-core/stamina/automaton/state.rb', line 199

def dfa_delta(symbol)
  return nil if symbol.nil?
  edge = @out_edges.find{|e| e.symbol==symbol}
  edge.nil? ? nil : edge.target
end

#dfa_step(symbol) ⇒ Object

Returns the state reached from this one with an input symbol, or nil if no such state. This method is not epsilon symbol aware. Moreover it is expected to be used on deterministic states only. If the state is not deterministic, the method returns one reachable state if such a state exists; which one is returned must be considered non deterministic.



146
147
148
149
 
# File 'lib/stamina-core/stamina/automaton/state.rb', line 146

def dfa_step(symbol)
  edge = @out_edges.find{|e| e.symbol==symbol}
  edge ? edge.target : nil
end

#epsilon_closure ⇒ Object

Computes the epsilon closure of this state. Epsilon closure is the set of all states reached from this one with a eps* input (sequence of zero or more epsilon symbols). The current state is always contained in the epsilon closure. Returns an unsorted array without duplicates; this array may not be modified.



156
157
158
 
# File 'lib/stamina-core/stamina/automaton/state.rb', line 156

def epsilon_closure()
  @epsilon_closure ||= compute_epsilon_closure(Set.new).to_a.freeze
end

#error!(value = true) ⇒ Object

Sets this state as an error state.



56
57
58
 
# File 'lib/stamina-core/stamina/automaton/state.rb', line 56

def error!(value = true)
  @data[:error] = value
end

#error? ⇒ Boolean

Returns true if this state is an error state, false otherwise.

Returns:

  • (Boolean) 


51
52
53
 
# File 'lib/stamina-core/stamina/automaton/state.rb', line 51

def error?
  !!@data[:error]
end

#in_adjacent_states ⇒ Object

Returns an array with adjacent states along an incoming edge (without duplicates).

Returned array may be modified.



122
123
124
 
# File 'lib/stamina-core/stamina/automaton/state.rb', line 122

def in_adjacent_states()
  (@in_edges.collect {|e| e.source}).uniq
end

#in_edges(sorted = false) ⇒ Object

Returns an array containing all incoming edges of the state. Edges are sorted if sorted is set to true. If two incoming edges have same symbol no order is guaranteed between them.

Returned array may be modified.



78
79
80
 
# File 'lib/stamina-core/stamina/automaton/state.rb', line 78

def in_edges(sorted=false)
  sorted ? @in_edges.sort : @in_edges.dup
end

#in_symbols(sorted = false) ⇒ Object

Returns an array with the different symbols appearing on incoming edges. Returned array does not contain duplicates. Symbols are sorted in the array if sorted is set to true.

Returned array may be modified.



96
97
98
99
 
# File 'lib/stamina-core/stamina/automaton/state.rb', line 96

def in_symbols(sorted=false)
  symbols = @in_edges.collect{|e| e.symbol}.uniq
  return sorted ? (symbols.sort &automaton.symbols_comparator) : symbols
end

#initial!(value = true) ⇒ Object

Sets this state as an initial state.



36
37
38
 
# File 'lib/stamina-core/stamina/automaton/state.rb', line 36

def initial!(value = true)
  @data[:initial] = value
end

#initial? ⇒ Boolean

Returns true if this state is an initial state, false otherwise.

Returns:

  • (Boolean) 


31
32
33
 
# File 'lib/stamina-core/stamina/automaton/state.rb', line 31

def initial?
  !!@data[:initial]
end

#inspect ⇒ Object

Returns a string representation



215
216
217
 
# File 'lib/stamina-core/stamina/automaton/state.rb', line 215

def inspect
  's' << @index.to_s
end

#out_adjacent_states ⇒ Object

Returns an array with adjacent states along an outgoing edge (whithout duplicates).

Returned array may be modified.



130
131
132
 
# File 'lib/stamina-core/stamina/automaton/state.rb', line 130

def out_adjacent_states()
  (@out_edges.collect {|e| e.target}).uniq
end

#out_edges(sorted = false) ⇒ Object

Returns an array containing all outgoing edges of the state. Edges are sorted if sorted is set to true. If two outgoing edges have same symbol no order is guaranteed between them.

Returned array may be modified.



87
88
89
 
# File 'lib/stamina-core/stamina/automaton/state.rb', line 87

def out_edges(sorted=false)
  sorted ? @out_edges.sort : @out_edges.dup
end

#out_symbols(sorted = false) ⇒ Object

Returns an array with the different symbols appearing on outgoing edges. Returned array does not contain duplicates. Symbols are sorted in the array if sorted is set to true.

Returned array may be modified.



106
107
108
109
 
# File 'lib/stamina-core/stamina/automaton/state.rb', line 106

def out_symbols(sorted=false)
  symbols = @out_edges.collect{|e| e.symbol}.uniq
  return sorted ? (symbols.sort &automaton.symbols_comparator) : symbols
end

#sink? ⇒ Boolean

Checks if this state is a sink state or not. Sink states are defined as non accepting states having no outgoing transition or only loop transitions.

Returns:

  • (Boolean) 


69
70
71
 
# File 'lib/stamina-core/stamina/automaton/state.rb', line 69

def sink?
  !accepting? && out_edges.all?{|e| e.target==self}
end

#step(symbol) ⇒ Object

Returns reachable states from this one with an input symbol. Returned array does not contain duplicates and may be modified. This method if not epsilon symbol aware.



137
138
139
 
# File 'lib/stamina-core/stamina/automaton/state.rb', line 137

def step(symbol)
  @out_edges.select{|e| e.symbol==symbol}.collect{|e| e.target}
end

#to_s ⇒ Object

Returns a string representation



220
221
222
 
# File 'lib/stamina-core/stamina/automaton/state.rb', line 220

def to_s
  's' << @index.to_s
end