Class: Stamina::Automaton
- Inherits:
-
Object
- Object
- Stamina::Automaton
- Includes:
- Walking, Classifier, Markable
- Defined in:
- lib/stamina/automaton.rb,
lib/stamina/automaton/walking.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
-
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.
-
-
Why using State methods State#step and State#delta ? The Automaton class includes the Walking module by default, which is much more powerful !
-
The constructor of this class executes the argument block (between
do
andend
) 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. -
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 fors[:initial]
if s is a State -
s.initial!
is a shortcut fors[:initial]=true
if s is a State -
Similar shortcuts are available for :accepting and :error
-
e.symbol
is a shortcut fore[:symbol]
if e is an Edge -
e.symbol='a'
is a shortcut fore[: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:
-
Why updating an automaton ? Building a fresh one is much more clean and efficient ! This is particularly true for removals.
-
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: Walking Classes: Edge, State
Instance Attribute Summary collapse
-
#edges ⇒ Object
readonly
State list and edge list of the automaton.
-
#states ⇒ Object
readonly
State list and edge list of the automaton.
Instance Method Summary collapse
-
#add_automaton(what, clear_names = true) ⇒ Object
Adds all states and transitions (as copies) from a different automaton.
-
#add_edge(from, to, data) ⇒ Object
(also: #create_edge, #connect)
Adds a new edge, connecting from and to states of the automaton.
-
#add_n_states(n, data = {}) ⇒ Object
(also: #create_n_states)
Adds n new states in the automaton.
-
#add_state(data = {}) ⇒ Object
(also: #create_state)
Adds a new state.
-
#adjacent_states(state) ⇒ Object
Returns an array with adjacent states (along incoming and outgoing edges) of state.
-
#alphabet ⇒ Object
Returns the alphabet of the automaton.
-
#alphabet=(alph) ⇒ Object
Sets the aphabet of the automaton.
-
#deterministic? ⇒ Boolean
Returns true if the automaton is deterministic, false otherwise.
-
#drop_edge(edge) ⇒ Object
(also: #delete_edge)
Drops an edge in the automaton.
-
#drop_edges(*edges) ⇒ Object
(also: #delete_edges)
Drops all edges passed as parameters.
-
#drop_state(state) ⇒ Object
(also: #delete_state)
Drops a state of the automaton, as well as all connected edges to that state.
-
#drop_states(*states) ⇒ Object
Drops all states passed as parameter as well as all their connected edges.
-
#dup ⇒ Object
Constructs a replica of this automaton and returns a copy.
-
#each_edge ⇒ Object
Calls block for each edge of the automaton edge list.
-
#each_state ⇒ Object
Calls block for each state of the automaton state list.
-
#edge_count ⇒ Object
Returns the number of edges.
-
#get_state(name) ⇒ Object
Returns state associated with the supplied state name, throws an exception if no such state can be found.
-
#in_adjacent_states(state) ⇒ Object
Returns an array with adjacent states (along incoming edges) of state.
-
#in_edges(state, sorted = false) ⇒ Object
Returns an array with incoming edges of state.
-
#in_symbols(state, sorted = false) ⇒ Object
Returns an array with the different symbols appearing on incoming edges of state.
-
#initial_state ⇒ Object
Returns the initial state of the automaton.
-
#initial_states ⇒ Object
Collects all initial states of this Automaton and returns it.
-
#initialize(onself = true, &block) ⇒ Automaton
constructor
Creates an empty automaton and executes the block passed as argument.
-
#ith_edge(i) ⇒ Object
Returns the i-th edge of the edge list.
-
#ith_edges(*i) ⇒ Object
Returns the i-th edges of the edge list.
-
#ith_state(i) ⇒ Object
Returns the i-th state of the state list.
-
#ith_states(*i) ⇒ Object
Returns the i-th states of the state list.
-
#order_states(&block) ⇒ Object
Uses a comparator block to reorder the state list.
-
#out_adjacent_states(state) ⇒ Object
Returns an array with adjacent states (along outgoing edges) of state.
-
#out_edges(state, sorted = false) ⇒ Object
Returns an array with outgoing edges of state.
-
#out_symbols(state, sorted = false) ⇒ Object
Returns an array with the different symbols appearing on outgoing edges of state.
-
#state_count ⇒ Object
Returns the number of states.
-
#symbols_comparator ⇒ Object
Returns a symbols comparator taking epsilon symbols into account.
-
#to_dot(&rewriter) ⇒ Object
Generates a dot output from an automaton.
Methods included from Classifier
#correctly_classify?, #signature
Methods included from Walking
#accepts?, #delta, #dfa_delta, #dfa_reached, #dfa_split, #dfa_step, #label_of, #parses?, #reached, #rejects?, #split, #step
Methods included from Markable
#[], #[]=, #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
546 547 548 549 550 551 552 553 554 555 556 557 558 559 560 561 562 563 564 565 |
# File 'lib/stamina/automaton.rb', line 546 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
511 512 513 |
# File 'lib/stamina/automaton.rb', line 511 def edges @edges end |
#states ⇒ Object (readonly)
State list and edge list of the automaton
511 512 513 |
# File 'lib/stamina/automaton.rb', line 511 def states @states end |
Instance Method Details
#add_automaton(what, clear_names = true) ⇒ Object
Adds all states and transitions (as copies) from a different automaton. Returns the initial state of the added part. 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. None of the added states are made initial.
881 882 883 884 885 886 887 888 889 890 891 892 |
# File 'lib/stamina/automaton.rb', line 881 def add_automaton(what,clear_names=true) map_what_self = {} what.states.each do |state| map_what_self[state]=add_state(state.data) map_what_self[state][:name]=nil if clear_names map_what_self[state][:initial]=false end what.edges.each do |edge| add_edge(map_what_self[edge.from],map_what_self[edge.to],edge.data) end map_what_self[what.initial_state] 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.
858 859 860 861 862 863 864 865 866 867 868 869 870 871 872 |
# File 'lib/stamina/automaton.rb', line 858 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.
834 835 836 837 838 839 840 |
# File 'lib/stamina/automaton.rb', line 834 def add_n_states(n, data={}) created = [] n.times do |i| created << add_state(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.
813 814 815 816 817 818 819 820 821 822 823 824 825 |
# File 'lib/stamina/automaton.rb', line 813 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)
738 |
# File 'lib/stamina/automaton.rb', line 738 def adjacent_states(state) to_state(state).adjacent_states() end |
#alphabet ⇒ Object
Returns the alphabet of the automaton.
1123 1124 1125 |
# File 'lib/stamina/automaton.rb', line 1123 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.
1131 1132 1133 1134 1135 |
# File 'lib/stamina/automaton.rb', line 1131 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 |
#deterministic? ⇒ Boolean
Returns true if the automaton is deterministic, false otherwise
1107 1108 1109 1110 |
# File 'lib/stamina/automaton.rb', line 1107 def deterministic? @deterministic = @states.reject{|s| s.deterministic?}.empty? if @deterministic.nil? @deterministic 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.
980 981 982 983 984 985 986 987 988 989 990 991 |
# File 'lib/stamina/automaton.rb', line 980 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.
1003 1004 1005 1006 1007 1008 1009 1010 1011 1012 1013 1014 1015 1016 1017 1018 1019 1020 |
# File 'lib/stamina/automaton.rb', line 1003 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.
913 914 915 916 917 918 919 920 921 922 923 924 925 926 927 |
# File 'lib/stamina/automaton.rb', line 913 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.
940 941 942 943 944 945 946 947 948 949 950 951 952 953 954 955 956 957 958 959 960 961 962 963 964 965 966 967 968 969 970 |
# File 'lib/stamina/automaton.rb', line 940 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 ⇒ Object
Constructs a replica of this automaton and returns a copy. This copy can be modified in whatever way without affecting the original automaton.
897 898 899 900 901 902 |
# File 'lib/stamina/automaton.rb', line 897 def dup Automaton.new(false) do |fa| initial = fa.add_automaton(self,false) initial[:initial] = true unless initial.nil? end end |
#each_edge ⇒ Object
Calls block for each edge of the automaton edge list. Edges are enumerated in index order.
666 |
# File 'lib/stamina/automaton.rb', line 666 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.
660 |
# File 'lib/stamina/automaton.rb', line 660 def each_state() @states.each {|s| yield s if block_given?} end |
#edge_count ⇒ Object
Returns the number of edges
588 |
# File 'lib/stamina/automaton.rb', line 588 def edge_count() @edges.size end |
#get_state(name) ⇒ Object
Returns state associated with the supplied state name, throws an exception if no such state can be found.
608 609 610 611 612 613 614 615 616 617 |
# File 'lib/stamina/automaton.rb', line 608 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 |
#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)
752 |
# File 'lib/stamina/automaton.rb', line 752 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.
680 |
# File 'lib/stamina/automaton.rb', line 680 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.
709 |
# File 'lib/stamina/automaton.rb', line 709 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.
791 792 793 |
# File 'lib/stamina/automaton.rb', line 791 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.
777 778 779 780 |
# File 'lib/stamina/automaton.rb', line 777 def initial_states @initials = compute_initial_states if @initials.nil? or @initials.empty? @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)
637 638 639 640 641 642 643 |
# File 'lib/stamina/automaton.rb', line 637 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)
652 653 654 |
# File 'lib/stamina/automaton.rb', line 652 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)
597 598 599 600 601 602 603 |
# File 'lib/stamina/automaton.rb', line 597 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)
626 627 628 |
# File 'lib/stamina/automaton.rb', line 626 def ith_states(*i) i.collect{|j| ith_state(j)} end |
#order_states(&block) ⇒ Object
Uses a comparator block to reorder the state list.
1214 1215 1216 1217 1218 1219 1220 |
# File 'lib/stamina/automaton.rb', line 1214 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)
766 |
# File 'lib/stamina/automaton.rb', line 766 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)
695 |
# File 'lib/stamina/automaton.rb', line 695 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)
724 |
# File 'lib/stamina/automaton.rb', line 724 def out_symbols(state, sorted=false) to_state(state).out_symbols(sorted) end |
#state_count ⇒ Object
Returns the number of states
585 |
# File 'lib/stamina/automaton.rb', line 585 def state_count() @states.size end |
#symbols_comparator ⇒ Object
Returns a symbols comparator taking epsilon symbols into account. Comparator is provided as Proc instance which is a lambda function.
574 575 576 577 578 579 580 581 582 |
# File 'lib/stamina/automaton.rb', line 574 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_dot(&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}”}
1179 1180 1181 1182 1183 1184 1185 1186 1187 1188 1189 1190 1191 1192 1193 1194 1195 1196 1197 1198 1199 1200 1201 1202 1203 1204 1205 1206 1207 1208 |
# File 'lib/stamina/automaton.rb', line 1179 def to_dot(&rewriter) unless rewriter to_dot do |elm, kind| case kind when :automaton {:rankdir => "LR"} when :state {:shape => (elm.accepting? ? "doublecircle" : "circle"), :style => "filled", :color => "black", :fillcolor => (elm.initial? ? "green" : (elm.error? ? "red" : "white"))} when :edge {:label => elm.symbol.nil? ? '' : elm.symbol.to_s} end end else buffer = "digraph G {\n" attrs = attributes2dot(rewriter.call(self, :automaton)) buffer << " graph [#{attrs}];\n" states.each do |s| 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 |