Class: Stamina::Automaton

Inherits:
Object
  • Object
show all
Includes:
Metrics, Walking, Markable
Defined in:
lib/stamina-core/stamina/automaton.rb,
lib/stamina-core/stamina/automaton/edge.rb,
lib/stamina-core/stamina/automaton/hide.rb,
lib/stamina-core/stamina/automaton/state.rb,
lib/stamina-core/stamina/automaton/strip.rb,
lib/stamina-core/stamina/automaton/compose.rb,
lib/stamina-core/stamina/automaton/metrics.rb,
lib/stamina-core/stamina/automaton/walking.rb,
lib/stamina-core/stamina/automaton/complete.rb,
lib/stamina-core/stamina/automaton/minimize.rb,
lib/stamina-core/stamina/automaton/complement.rb,
lib/stamina-core/stamina/automaton/determinize.rb,
lib/stamina-core/stamina/automaton/equivalence.rb,
lib/stamina-core/stamina/automaton/minimize/hopcroft.rb,
lib/stamina-core/stamina/automaton/minimize/pitchies.rb

Overview

Automaton data-structure.

Examples

The following example uses a lot of useful DRY shortcuts, so, if it does not fit you needs then, read on!):

# Building an automaton for the regular language a(ba)*
fa = Automaton.new do
  add_state(:initial => true)
  add_state(:accepting => true)
  connect(0,1,'a')
  connect(1,0,'b')
end

# It accepts 'a b a b a', rejects 'a b' as well as ''
puts fa.accepts?('? a b a b a')   # prints true
puts fa.accepts?('? a b')         # prints false
puts fa.rejects?('?')            # prints true

Four things you need to know

  1. Automaton, State and Edge classes implement a Markable design pattern, that is, you can read and write any key/value pair you want on them using the [] and []= operators. Note that the following keys are used by Stamina itself, with the obvious semantics (for automata and transducers):

    • :initial, :accepting, :error on State; expected to be true or false (nil and ommitted are considered as false). Shortcuts for querying and setting these attributes are provided by State.

    • :symbol on Edge, with shortcuts as well on Edge. The convention is to use nil for the epsilon symbol (aka non observable) on non deterministic automata.

    The following keys are reserved for future extensions:

    • :output on State and Edge.

    • :short_prefix on State.

    See also the “About states and edges” subsection of the design choices.

  2. Why using State methods State#step and State#delta ? The Automaton class includes the Walking module by default, which is much more powerful !

  3. The constructor of this class executes the argument block (between do and end) with instance_eval by default. You won’t be able to invoke the methods defined in the scope of your block in such a case. See new for details.

  4. This class has not been designed with efficiency in mind. If you experiment performance problems, read the “About Automaton modifications” sub section of the design choices.

Design choices

This section fully details the design choices that has been made for the implementation of the Automaton data structure used by Stamina. It is provided because Automaton is one of the core classes of Stamina, that probably all users (and contributors) will use. Automaton usage is really user-friendly, so you are normally not required to read this section in the first place ! Read it only if of interest for you, or if you experiment unexpected results.

One Automaton class only

One class only implements all kinds of automata: deterministic, non-deterministic, transducers, prefix-tree-acceptors, etc. The Markable design pattern on states and edges should allow you to make anything you could find useful with this class.

Adjacency-list graph

This class implements an automaton using a adjacent-list graph structure. The automaton has state and edge array lists and exposes them through the states and edges accessors. In order to let users enjoy the enumerability of Ruby’s arrays while allowing automata to be modified, these arrays are externaly modifiable. However, users are not expected to modify them! and future versions of Stamina will certainly remove this ability.

Indices exposed

State and Edge indices in these arrays are exposed by this class. Unless stated explicitely, all methods taking state or edge arguments support indices as well. Moreover, ith_state, ith_states, ith_edge and ith_edges methods provide powerful access to states and edges by indices. All these methods are robust to invalid indices (and raise an IndexError if incorrectly invoked) but do not allow negative indexing (unlike ruby arrays).

States and edges know their index in the corresponding array and expose them through the (read-only) index accessor. These indices are always valid; without deletion of states or edges in the automaton, they are guaranteed not to change. Indices saved in your own variables must be considered deprecated each time you perform a deletion ! That’s the only rule to respect if you plan to use indices.

Indices exposition may seem a strange choice and could be interpreted as breaking OOP’s best practice. You are not required to use them but, as will quiclky appear, using them is really powerful and leads to beautiful code! If you don’t remove any state or edge, this class guarantees that indices are assigned in the same order as invocations of add_state and add_edge (as well as their plural forms and aliases).

About states and edges

Edges know their source and target states, which are exposed through the source and target (read-only) accessors (also aliased as from and to). States keep their incoming and outgoing edges in arrays, which are accessible (in fact, a copy) using State#in_edges and State#out_edges. If you use them for walking the automaton in a somewhat standard way, consider using the Walking module instead!

Common attributes of states and edges are installed using the Markable pattern itself:

  • :initial, :accepting and :error on states. These attributes are expected to be true or false (nil and ommitted are also supported and both considered as false).

  • :symbol on edges. Any object you want as long as it responds to the <=> operator. Also, the convention is to use nil for the epsilon symbol (aka non observable) on non deterministic automata.

In addition, useful shortcuts are available:

  • s.initial? is a shortcut for s[:initial] if s is a State

  • s.initial! is a shortcut for s[:initial]=true if s is a State

  • Similar shortcuts are available for :accepting and :error

  • e.symbol is a shortcut for e[:symbol] if e is an Edge

  • e.symbol='a' is a shortcut for e[:symbol]='a' if e is an Edge

Following keys should be considered reserved by Stamina for future extensions:

  • :output on State and Edge.

  • :short_prefix on State.

About Automaton modifications

This class has not been implemented with efficiency in mind. In particular, we expect the vast majority of Stamina core algorithms considering automata as immutable values. For this reason, the Automaton class does not handle modifications really efficiently.

So, if you experiment performance problems, consider what follows:

  1. Why updating an automaton ? Building a fresh one is much more clean and efficient ! This is particularly true for removals.

  2. If you can create multiples states or edges at once, consider the plural form of the modification methods: add_n_states and drop_states. Those methods are optimized for multiple updates.

Detailed API

Defined Under Namespace

Modules: Metrics, Minimize, Walking Classes: Compose, Determinize, Edge, Equivalence, State

Instance Attribute Summary collapse

Class Method Summary collapse

Instance Method Summary collapse

Methods included from Walking

#accepts?, #delta, #dfa_delta, #dfa_reached, #dfa_split, #dfa_step, #label_of, #parses?, #reached, #rejects?, #split, #step

Methods included from Metrics

#accepting_ratio, #alphabet_size, #avg_degree, #depth, #error_ratio

Methods included from Markable

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

Constructor Details

#initialize(onself = true, &block) ⇒ Automaton

Creates an empty automaton and executes the block passed as argument. The onself argument dictates the way block is executed:

  • when set to false, the block is executed traditionnally (i.e. using yield). In this case, methods invocations must be performed on the automaton object passed as block argument.

  • when set to true (by default) the block is executed in the context of the automaton itself (i.e. with instance_eval), allowing call of its methods without prefixing them by the automaton variable. The automaton still passes itself as first block argument. Note that in this case, you won’t be able to invoke a method defined in the scope of your block.

Example:

# The DRY way to do:
Automaton.new do |automaton|     # automaton will not be used here, but it is passed
  add_state(:initial => true)
  add_state(:accepting => true)
  connect(0, 1, 'a')
  connect(1, 0, 'b')

  # method_in_caller_scope()     # commented because not allowed here !!
end

# The other way:
Automaton.new(false) do |automaton|      # automaton MUST be used here
  automaton.add_state(:initial => true)
  automaton.add_state(:accepting => true)
  automaton.connect(0, 1, 'a')
  automaton.connect(1, 0, 'b')

  method_in_caller_scope()               # allowed in this variant !!
end



176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
 
# File 'lib/stamina-core/stamina/automaton.rb', line 176

def initialize(onself=true, &block) # :yields: automaton
  @states = []
  @edges = []
  @initials = nil
  @alphabet = nil
  @deterministic = nil

  # if there's a block, execute it now!
  if block_given?
    if onself
      if RUBY_VERSION >= "1.9.0"
        instance_exec(self, &block)
      else
        instance_eval(&block)
      end
    else
      block.call(self)
    end
  end
end

Instance Attribute Details

#edges ⇒ Object (readonly)

State list and edge list of the automaton



141
142
143
 
# File 'lib/stamina-core/stamina/automaton.rb', line 141

def edges
  @edges
end

#states ⇒ Object (readonly)

State list and edge list of the automaton



141
142
143
 
# File 'lib/stamina-core/stamina/automaton.rb', line 141

def states
  @states
end

Class Method Details

.coerce(arg) ⇒ Object

Coerces ‘arg` to an automaton



198
199
200
201
202
203
204
205
206
 
# File 'lib/stamina-core/stamina/automaton.rb', line 198

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

.parse(str) ⇒ Object

Parses an automaton using ADL



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

def self.parse(str)
  ADL::parse_automaton(str)
end

Instance Method Details

#add_automaton(fa, clear_names = true) ⇒ Object

Adds all states and transitions (as copies) from a different automaton. None of the added states are made initial. Returns the (associated state of the) initial state of the added part.

This method is deprecated and should not be used anymore. Use dup instead.

In order to ensure that names of the new states do not clash with names of existing states, state names may have to be removed from added states; this is the case if clear_names is set to true.



533
534
535
536
537
538
539
540
541
 
# File 'lib/stamina-core/stamina/automaton.rb', line 533

def add_automaton(fa, clear_names = true)
  initial = nil
  fa.dup(self){|source,target|
    initial = target if target.initial?
    target[:initial] = false
    target[:name] = nil if clear_names
  }
  initial
end

#add_edge(from, to, data) ⇒ Object Also known as: create_edge, connect

Adds a new edge, connecting from and to states of the automaton.

Arguments:

  • from: either a State or a valid state index (Integer).

  • to: either a State or a valid state index (Integer).

  • data: user data to attach to the created edge (see Automaton documentation).

Raises:

  • IndexError if from is an Integer but not in [0..state_count)

  • IndexError if to is an Integer but not in [0..state_count)

  • ArgumentError if from is not a valid state for this automaton.

  • ArgumentError if to is not a valid state for this automaton.

  • ArgumentError if data is not a valid edge data.



504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
 
# File 'lib/stamina-core/stamina/automaton.rb', line 504

def add_edge(from, to, data)
  from, to, data = to_state(from), to_state(to), to_valid_edge_data(data)

  # create edge, install it, add it to edge-list
  edge = Edge.new(self, edge_count, data, from, to)
  @edges << edge
  from.send(:add_outgoing_edge, edge)
  to.send(:add_incoming_edge, edge)

  # let automaton know that something has changed
  state_changed(:edge_added, edge)

  # return created edge
  edge
end

#add_n_states(n, data = {}) ⇒ Object Also known as: create_n_states

Adds n new states in the automaton. Created states are returned as an ordered array (order of states according to their index in state list).

data is duplicated for each created state.



480
481
482
483
484
485
486
 
# File 'lib/stamina-core/stamina/automaton.rb', line 480

def add_n_states(n, data={})
  created = []
  n.times do |i|
    created << add_state(block_given? ? data.merge(yield(i)) : data.dup)
  end
  created
end

#add_state(data = {}) ⇒ Object Also known as: create_state

Adds a new state.

Arguments:

  • data: user-data to attach to the state (see Automaton documentation).

Raises:

  • ArgumentError if data is not a valid state data.



459
460
461
462
463
464
465
466
467
468
469
470
471
 
# File 'lib/stamina-core/stamina/automaton.rb', line 459

def add_state(data={})
  data = to_valid_state_data(data)

  # create new state, add it to state-list
  state = State.new(self, state_count, data)
  @states <<  state

  # let the automaton know that something has changed
  state_changed(:state_added, state)

  # return created state
  state
end

#adjacent_states(state) ⇒ Object

Returns an array with adjacent states (along incoming and outgoing edges) of state. Returned array does not contain duplicates; it may be modified.

If state is an Integer, this method returns the adjacent states of the state’th state in the state list.

Raises:

  • IndexError if state is an Integer and state<0 or state>=state_count.

  • ArgumentError if state is not a valid state (not a state or not from this automaton)



382
 
# File 'lib/stamina-core/stamina/automaton.rb', line 382

def adjacent_states(state) to_state(state).adjacent_states() end

#alphabet ⇒ Object

Returns the alphabet of the automaton.



781
782
783
 
# File 'lib/stamina-core/stamina/automaton.rb', line 781

def alphabet
  @alphabet || deduce_alphabet
end

#alphabet=(alph) ⇒ Object

Sets the aphabet of the automaton. alph is expected to be an array without nil nor duplicated. This method raises an ArgumentError otherwise. Such an error is also raised if a symbol used on the automaton edges is not included in alph.

Raises:

  • (ArgumentError) 


789
790
791
792
793
 
# File 'lib/stamina-core/stamina/automaton.rb', line 789

def alphabet=(alph)
  raise ArgumentError, "Invalid alphabet" unless alph.uniq.compact.size==alph.size
  raise ArgumentError, "Invalid alphabet" unless deduce_alphabet.reject{|s| alph.include?(s)}.empty?
  @alphabet = alph.sort
end

#complement ⇒ Object

Returns the complement automaton.

A complement automaton is simply a complete automaton with all state labels flipped.



10
11
12
 
# File 'lib/stamina-core/stamina/automaton/complement.rb', line 10

def complement
  dup.complement!
end

#complement! ⇒ Object

Complements this automaton



17
18
19
20
21
22
23
 
# File 'lib/stamina-core/stamina/automaton/complement.rb', line 17

def complement!
  complete!
  each_state do |s|
    s[:accepting] = !s.accepting?
  end
  self
end

#complete ⇒ Object

Returns a completed copy of this automaton



15
16
17
 
# File 'lib/stamina-core/stamina/automaton/complete.rb', line 15

def complete
  self.dup.complete!
end

#complete!(sink_data = {:initial => false, :accepting => false, :error => false}) ⇒ Object

Completes this automaton.



22
23
24
25
26
27
28
29
30
31
32
33
34
 
# File 'lib/stamina-core/stamina/automaton/complete.rb', line 22

def complete!(sink_data = {:initial => false, :accepting => false, :error => false})
  alph = alphabet
  sink = add_state(sink_data)
  each_state do |s|
    out_symbols = s.out_symbols
    (alph-out_symbols).each do |symbol|
      connect(s, sink, symbol)
    end
  end
  adj = sink.adjacent_states
  drop_state(sink) if adj.empty? or adj == [sink]
  self
end

#complete? ⇒ Boolean

Checks if this automaton is complete

Returns:

  • (Boolean) 


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

def complete?
  alph = alphabet
  states.find{|s| !(alphabet - s.out_symbols).empty?}.nil?
end

#compose(*automata) ⇒ Object

class Compose



76
77
78
 
# File 'lib/stamina-core/stamina/automaton/compose.rb', line 76

def compose(*automata)
  Automaton::Compose.execute([self] + automata)
end

#deterministic? ⇒ Boolean

Returns true if the automaton is deterministic, false otherwise

Returns:

  • (Boolean) 


765
766
767
768
 
# File 'lib/stamina-core/stamina/automaton.rb', line 765

def deterministic?
  @deterministic = @states.all?{|s| s.deterministic?} if @deterministic.nil?
  @deterministic
end

#determinize ⇒ Object

Determinizes this automaton by removing explicit non-determinism as well as all espilon moves.



99
100
101
 
# File 'lib/stamina-core/stamina/automaton/determinize.rb', line 99

def determinize
  Determinize.execute(self)
end

#drop_edge(edge) ⇒ Object Also known as: delete_edge

Drops an edge in the automaton. If edge is an integer, the edge-th edge of the edge list is removed. This method returns the automaton itself.

Raises:

  • IndexError if edge is an Integer but not in [0..edge_count)

  • ArgumentError if edge is not a valid edge for this automaton.



638
639
640
641
642
643
644
645
646
647
648
649
 
# File 'lib/stamina-core/stamina/automaton.rb', line 638

def drop_edge(edge)
  edge = to_edge(edge)
  @edges.delete_at(edge.index)
  edge.from.send(:drop_outgoing_edge,edge)
  edge.to.send(:drop_incoming_edge,edge)
  edge.index.upto(edge_count-1) do |i|
    @edges[i].send(:index=, i)
  end
  edge.send(:index=,-1)
  state_changed(:edge_dropped, edge)
  self
end

#drop_edges(*edges) ⇒ Object Also known as: delete_edges

Drops all edges passed as parameters. Arguments may be edge objects, as well as valid edge indices. Duplicates are even supported. This method has no effect on the automaton and raises an error if some edge argument is not valid.

Raises:

  • ArgumentError if one edge in edges is not a valid edge of this automaton.



661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
 
# File 'lib/stamina-core/stamina/automaton.rb', line 661

def drop_edges(*edges)
  # check edges first
  edges = edges.collect{|e| to_edge(e)}.uniq

  # remove all edges
  edges.each do |e|
    @edges.delete(e)
    e.from.send(:drop_outgoing_edge,e)
    e.to.send(:drop_incoming_edge,e)
    e.send(:index=, -1)
    state_changed(:edge_dropped, e)
  end
  @edges.each_with_index do |e,i|
    e.send(:index=,i)
  end

  self
end

#drop_state(state) ⇒ Object Also known as: delete_state

Drops a state of the automaton, as well as all connected edges to that state. If state is an integer, the state-th state of the state list is removed. This method returns the automaton itself.

Raises:

  • IndexError if edge is an Integer but not in [0..edge_count)

  • ArgumentError if edge is not a valid edge for this automaton.



571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
 
# File 'lib/stamina-core/stamina/automaton.rb', line 571

def drop_state(state)
  state = to_state(state)
  # remove edges first: drop_edges ensures that edge list is coherent
  drop_edges(*(state.in_edges + state.out_edges).uniq)

  # remove state now and renumber
  @states.delete_at(state.index)
  state.index.upto(state_count-1) do |i|
    @states[i].send(:index=, i)
  end
  state.send(:index=, -1)

  state_changed(:state_dropped, state)
  self
end

#drop_states(*states) ⇒ Object

Drops all states passed as parameter as well as all their connected edges. Arguments may be state instances, as well as valid state indices. Duplicates are even supported. This method has no effect on the automaton and raises an error if some state argument is not valid.

Raises:

  • ArgumentError if one state in states is not a valid state of this automaton.



598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
 
# File 'lib/stamina-core/stamina/automaton.rb', line 598

def drop_states(*states)
  # check states first
  states = states.collect{|s| to_state(s)}.uniq.sort
  edges  = states.collect{|s| (s.in_edges + s.out_edges).uniq}.flatten.uniq.sort

  # Remove all edges, we do not use drop_edges to avoid spending too much
  # time reindexing edges. Moreover, we can do it that way because we take
  # edges in reverse indexing order (has been sorted previously)
  until edges.empty?
    edge = edges.pop
    edge.source.send(:drop_outgoing_edge,edge)
    edge.target.send(:drop_incoming_edge,edge)
    @edges.delete_at(edge.index)
    edge.send(:index=, -1)
    state_changed(:edge_dropped, edge)
  end

  # Remove all states, same kind of hack is used
  until states.empty?
    state = states.pop
    @states.delete_at(state.index)
    state.send(:index=, -1)
    state_changed(:state_dropped, state)
  end

  # sanitize state and edge lists
  @states.each_with_index {|s,i| s.send(:index=,i)}
  @edges.each_with_index {|e,i| e.send(:index=,i)}

  self
end

#dup(fa = Automaton.new) ⇒ Object

Constructs a replica of this automaton and returns a copy.

This copy can be modified in whatever way without affecting the original automaton.



549
550
551
552
553
554
555
556
557
558
559
560
 
# File 'lib/stamina-core/stamina/automaton.rb', line 549

def dup(fa = Automaton.new)
  added = states.collect do |source|
    target = fa.add_state(source.data.dup)
    yield(source, target) if block_given?
    target
  end
  edges.each do |edge|
    from, to = added[edge.from.index], added[edge.to.index]
    fa.connect(from, to, edge.data.dup)
  end
  fa
end

#each_edge ⇒ Object

Calls block for each edge of the automaton edge list. Edges are enumerated in index order.



310
 
# File 'lib/stamina-core/stamina/automaton.rb', line 310

def each_edge() @edges.each {|e| yield e if block_given?} end

#each_state ⇒ Object

Calls block for each state of the automaton state list. States are enumerated in index order.



304
 
# File 'lib/stamina-core/stamina/automaton.rb', line 304

def each_state() @states.each {|s| yield s if block_given?} end

#edge_count ⇒ Object

Returns the number of edges



232
 
# File 'lib/stamina-core/stamina/automaton.rb', line 232

def edge_count() @edges.size end

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

Checks if this automaton is equivalent to another one.

Automata must be both minimal and complete to guarantee that this method works.

Returns:

  • (Boolean) 


32
33
34
 
# File 'lib/stamina-core/stamina/automaton/equivalence.rb', line 32

def equivalent?(other)
  Equivalence.new.call(self, other)
end

#get_state(name) ⇒ Object

Returns state associated with the supplied state name, throws an exception if no such state can be found.

Raises:

  • (ArgumentError) 


252
253
254
255
256
257
258
259
260
261
 
# File 'lib/stamina-core/stamina/automaton.rb', line 252

def get_state(name)
  raise(ArgumentError, "String expected, #{name} found.", caller)\
    unless String === name
    result = states.find do |s|
      name == s[:name]
    end
  raise(ArgumentError, "State #{name} was not found", caller)\
    if result.nil?
  result
end

#hide(alph) ⇒ Object

Returns a copy of self where all symbols in ‘alph` have been replaced by nil.



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

def hide(alph)
  dup.hide!(alph)
end

#hide!(alph) ⇒ Object

Replaces all symbols in ‘alph` by nil in this automaton.



15
16
17
18
19
20
21
22
23
 
# File 'lib/stamina-core/stamina/automaton/hide.rb', line 15

def hide!(alph)
  new_alph = alphabet.to_a - alph.to_a
  h = Set.new(new_alph.to_a)
  each_edge do |edge|
    edge.symbol = nil unless h.include?(edge.symbol)
  end
  self.alphabet = new_alph
  self
end

#in_adjacent_states(state) ⇒ Object

Returns an array with adjacent states (along incoming edges) of state. Returned array does not contain duplicates; it may be modified.

If state is an Integer, this method returns the incoming adjacent states of the state’th state in the state list.

Raises:

  • IndexError if state is an Integer and state<0 or state>=state_count.

  • ArgumentError if state is not a valid state (not a state or not from this automaton)



396
 
# File 'lib/stamina-core/stamina/automaton.rb', line 396

def in_adjacent_states(state) to_state(state).in_adjacent_states() end

#in_edges(state, sorted = false) ⇒ Object

Returns an array with incoming edges of state. Edges are sorted by symbols if sorted is set to true. If two incoming edges have same symbol, no order is guaranteed between them. Returned array may be modified.

If state is an Integer, this method returns the incoming edges of the state’th state in the state list.

Raises:

  • IndexError if state is an Integer and state<0 or state>=state_count.

  • ArgumentError if state is not a valid state for this automaton.



324
 
# File 'lib/stamina-core/stamina/automaton.rb', line 324

def in_edges(state, sorted=false) to_state(state).in_edges(sorted) end

#in_symbols(state, sorted = false) ⇒ Object

Returns an array with the different symbols appearing on incoming edges of state. Returned array does not contain duplicates and may be modified; it is sorted if sorted is set to true.

If state is an Integer, this method returns the incoming symbols of the state’th state in the state list.

Raises:

  • IndexError if state is an Integer and state<0 or state>=state_count.

  • ArgumentError if state is not a valid state for this automaton.



353
 
# File 'lib/stamina-core/stamina/automaton.rb', line 353

def in_symbols(state, sorted=false) to_state(state).in_symbols(sorted) end

#initial_state ⇒ Object

Returns the initial state of the automaton. This method is expected to used on deterministic automata only. Unlike initial_states, it returns one State instance instead of an Array.

When used with a non deterministic automaton, it returns one of the states tagged as initial. Which one is returned must be considered a non deterministic choice. This method is not epsilon symbol aware.



437
438
439
 
# File 'lib/stamina-core/stamina/automaton.rb', line 437

def initial_state
  initial_states[0]
end

#initial_states ⇒ Object

Collects all initial states of this Automaton and returns it. Returned array does not contain duplicates and may be modified.

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



421
422
423
424
425
426
 
# File 'lib/stamina-core/stamina/automaton.rb', line 421

def initial_states
  if @initials.nil? or @initials.empty?
    @initials = compute_initial_states
  end
  @initials
end

#ith_edge(i) ⇒ Object

Returns the i-th edge of the edge list.

Raises:

  • ArgumentError unless i is an Integer

  • IndexError if i is not in [0..state_count)

Raises:

  • (ArgumentError) 


281
282
283
284
285
286
287
 
# File 'lib/stamina-core/stamina/automaton.rb', line 281

def ith_edge(i)
  raise(ArgumentError, "Integer expected, #{i} found.", caller)\
    unless Integer === i
  raise(ArgumentError, "Invalid edge index #{i}", caller)\
    unless i>=0 and i<edge_count
  @edges[i]
end

#ith_edges(*i) ⇒ Object

Returns the i-th edges of the edge list.

Raises:

  • ArgumentError unless all i are integers

  • IndexError unless all i are in [0..edge_count)



296
297
298
 
# File 'lib/stamina-core/stamina/automaton.rb', line 296

def ith_edges(*i)
  i.collect{|j| ith_edge(j)}
end

#ith_state(i) ⇒ Object

Returns the i-th state of the state list.

Raises:

  • ArgumentError unless i is an Integer

  • IndexError if i is not in [0..state_count)

Raises:

  • (ArgumentError) 


241
242
243
244
245
246
247
 
# File 'lib/stamina-core/stamina/automaton.rb', line 241

def ith_state(i)
  raise(ArgumentError, "Integer expected, #{i} found.", caller)\
    unless Integer === i
  raise(ArgumentError, "Invalid state index #{i}", caller)\
    unless i>=0 and i<state_count
  @states[i]
end

#ith_states(*i) ⇒ Object

Returns the i-th states of the state list.

Raises:

  • ArgumentError unless all i are integers

  • IndexError unless all i are in [0..state_count)



270
271
272
 
# File 'lib/stamina-core/stamina/automaton.rb', line 270

def ith_states(*i)
  i.collect{|j| ith_state(j)}
end

#keep(alph) ⇒ Object

Returns a copy of self where all symbols not in ‘alph` have been replaced by nil.



29
30
31
 
# File 'lib/stamina-core/stamina/automaton/hide.rb', line 29

def keep(alph)
  dup.keep!(alph)
end

#keep!(alph) ⇒ Object

Replaces all symbols not in ‘alph` by nil in this automaton.



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

def keep!(alph)
  hide!(self.alphabet.to_a - alph.to_a)
end

#minimal? ⇒ Boolean

Checks if this automaton is minimal.

Returns:

  • (Boolean) 


7
8
9
 
# File 'lib/stamina-core/stamina/automaton/minimize.rb', line 7

def minimal?
  self.minimize.state_count == self.state_count
end

#minimize(options = {}) ⇒ Object

Returns a minimized version of this automaton.

This method should only be called on deterministic automata.



16
17
18
 
# File 'lib/stamina-core/stamina/automaton/minimize.rb', line 16

def minimize(options = {})
  Minimize::Hopcroft.execute(self, options)
end

#order_states(&block) ⇒ Object

Uses a comparator block to reorder the state list.

Raises:

  • (ArgumentError) 


917
918
919
920
921
922
923
 
# File 'lib/stamina-core/stamina/automaton.rb', line 917

def order_states(&block)
  raise ArgumentError, "A comparator block must be given" unless block_given?
  raise ArgumentError, "A comparator block of arity 2 must be given" unless block.arity==2
  @states.sort!(&block)
  @states.each_with_index{|s,i| s.send(:index=, i)}
  self
end

#out_adjacent_states(state) ⇒ Object

Returns an array with adjacent states (along outgoing edges) of state. Returned array does not contain duplicates; it may be modified.

If state is an Integer, this method returns the outgoing adjacent states of the state’th state in the state list.

Raises:

  • IndexError if state is an Integer and state<0 or state>=state_count.

  • ArgumentError if state is not a valid state (not a state or not from this automaton)



410
 
# File 'lib/stamina-core/stamina/automaton.rb', line 410

def out_adjacent_states(state) to_state(state).out_adjacent_states() end

#out_edges(state, sorted = false) ⇒ Object

Returns an array with outgoing edges of state. Edges are sorted by symbols if sorted is set to true. If two incoming edges have same symbol, no order is guaranteed between them. Returned array may be modified.

If state is an Integer, this method returns the outgoing edges of the state’th state in the state list.

Raises:

  • IndexError if state is an Integer and state<0 or state>=state_count.

  • ArgumentError if state is not a valid state (not a state or not from this automaton)



339
 
# File 'lib/stamina-core/stamina/automaton.rb', line 339

def out_edges(state, sorted=false) to_state(state).out_edges(sorted) end

#out_symbols(state, sorted = false) ⇒ Object

Returns an array with the different symbols appearing on outgoing edges of state. Returned array does not contain duplicates and may be modified; it is sorted if sorted is set to true.

If state is an Integer, this method returns the outgoing symbols of the state’th state in the state list.

Raises:

  • IndexError if state is an Integer and state<0 or state>=state_count.

  • ArgumentError if state is not a valid state (not a state or not from this automaton)



368
 
# File 'lib/stamina-core/stamina/automaton.rb', line 368

def out_symbols(state, sorted=false) to_state(state).out_symbols(sorted) end

#state_count ⇒ Object

Returns the number of states



229
 
# File 'lib/stamina-core/stamina/automaton.rb', line 229

def state_count() @states.size end

#strip ⇒ Object

Returns a copy of this automaton with unreachable states removed



11
12
13
 
# File 'lib/stamina-core/stamina/automaton/strip.rb', line 11

def strip
  dup.strip!
end

#strip! ⇒ Object

Removes unreachable states from the initial ones



5
6
7
8
 
# File 'lib/stamina-core/stamina/automaton/strip.rb', line 5

def strip!
  depth(:reachable)
  drop_states(*states.select{|s| s[:reachable].nil?})
end

#symbols_comparator ⇒ Object

Returns a symbols comparator taking epsilon symbols into account. Comparator is provided as Proc instance which is a lambda function.



218
219
220
221
222
223
224
225
226
 
# File 'lib/stamina-core/stamina/automaton.rb', line 218

def symbols_comparator
  @symbols_comparator ||= Kernel.lambda do |a,b|
    if a==b then 0
    elsif a.nil? then -1
    elsif b.nil? then 1
    else a <=> b
    end
  end
end

#to_adl(buffer = "") ⇒ Object

Prints this automaton in ADL format



909
910
911
 
# File 'lib/stamina-core/stamina/automaton.rb', line 909

def to_adl(buffer = "")
  Stamina::ADL.print_automaton(self, buffer)
end

#to_cdfa ⇒ Object

Returns a canonical deterministic finite automaton



809
810
811
812
813
814
815
 
# File 'lib/stamina-core/stamina/automaton.rb', line 809

def to_cdfa
  cdfa = self
  cdfa = cdfa.determinize unless self.deterministic?
  cdfa = cdfa.complete    unless self.complete?
  cdfa = cdfa.minimize
  cdfa
end

#to_dfa ⇒ Object

Returns a deterministic finite automaton



804
805
806
 
# File 'lib/stamina-core/stamina/automaton.rb', line 804

def to_dfa
  self.deterministic? ? self : self.determinize
end

#to_dot(sort_states = true, &rewriter) ⇒ Object

Generates a dot output from an automaton. The rewriter block takes two arguments: the first one is a Markable instance (graph, state or edge), the second one indicates which kind of element is passed (through :automaton, :state or :edge symbol). The rewriter is expected to return a hash-like object providing dot attributes for the element.

When no rewriter is provided, a default one is used by default, providing the following behavior:

  • on :automaton

    => “LR”

  • on :state

    => “doublecircle/circle” (following accepting?),

    :style => "filled",
:fillcolor => "green/red/white" (if initial?/error?/else, respectively)

  • on edge

    {:label => “#{edge.symbol}”}



864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
 
# File 'lib/stamina-core/stamina/automaton.rb', line 864

def to_dot(sort_states = true, &rewriter)
  unless rewriter
    to_dot(sort_states) do |elm, kind|
      case kind
        when :automaton
          {:pack => true, :rankdir => "LR", :ranksep => 0, :margin => 0}
        when :state
          {:shape => (elm.accepting? ? "doublecircle" : "circle"),
           :style => "filled",
           :color => "black",
           :fillcolor => (elm.initial? ? "green" : (elm.error? ? "red" : "white")),
           :width => 0.6, :height => 0.6, :fixedsize => true
          }
        when :edge
          {:label => elm.symbol.nil? ? '' : elm.symbol.to_s,
           :arrowsize => 0.7}
      end
    end
  else
    buffer = "digraph G {\n"
    attrs = attributes2dot(rewriter.call(self, :automaton))
    buffer << "  graph [#{attrs}];\n"
    ss = if sort_states
      self.depth
      states.sort{|s1,s2| s1[:depth] <=> s2[:depth]}
    else
      self.states
    end
    ss.each do |s|
      s.remove_mark(:depth) if sort_states
      attrs = attributes2dot(rewriter.call(s, :state))
      buffer << "  #{s.index} [#{attrs}];\n"
    end
    edges.each do |e|
      attrs = attributes2dot(rewriter.call(e, :edge))
      buffer << "  #{e.source.index} -> #{e.target.index} [#{attrs}];\n"
    end
    buffer << "}\n"
  end
end

#to_fa ⇒ Object

Returns a finite automaton



799
800
801
 
# File 'lib/stamina-core/stamina/automaton.rb', line 799

def to_fa
  self
end

#to_reglang ⇒ Object

Returns a regular language



818
819
820
 
# File 'lib/stamina-core/stamina/automaton.rb', line 818

def to_reglang
  RegLang.new(self)
end