Class: Lernen::Automaton::TransitionSystem
- Inherits:
-
Object
- Object
- Lernen::Automaton::TransitionSystem
- Defined in:
- lib/lernen/automaton/transition_system.rb
Overview
TransitionSystem represents a labelled transition system.
We assume that this transition system is deterministic and complete; thus, the transition function should be defined for all states and input characters, and the destination configuration of a transition should be one.
Also, this transition system has an output value for each transition. From this point of view, this definition is much like Mealy machines. However, this class is more generic. Actually, this is a superclass of Moore machines, DFA, etc.
Note that this class is abstract. We should implement the following method:
-
‘#type`
-
‘#initial_conf`
-
‘#step(conf, input)`
-
‘#to_graph`
Class Method Summary collapse
-
.find_separating_word(alphabet, automaton1, automaton2) ⇒ Object
Finds a separating word between ‘automaton1` and `automaton2`.
-
.random_transition_function(alphabet:, min_state_size: 5, max_state_size: 10, num_reachable_paths: 2, random: Random) ⇒ Object
Generates a transition function randomly.
Instance Method Summary collapse
-
#initial_conf ⇒ Object
Returns the initial configuration.
-
#run(word) ⇒ Object
Runs transitions from the initial configuration with the given word.
-
#step(conf, input) ⇒ Object
Runs a transition from the given configuration with the given input.
-
#to_dot ⇒ Object
Returns a [GraphViz](graphviz.org) DOT diagram of this transition system.
-
#to_graph ⇒ Object
Returns a graph of this transition system.
-
#to_mermaid(direction: "TD") ⇒ Object
Returns a [Mermaid](mermaid.js.org) diagram of this transition system.
-
#type ⇒ Object
Returns the automaton type.
Class Method Details
.find_separating_word(alphabet, automaton1, automaton2) ⇒ Object
Finds a separating word between ‘automaton1` and `automaton2`.
: [Conf, In, Out] (
Array[In] alphabet,
TransitionSystem[Conf, In, Out] automaton1,
TransitionSystem[Conf, In, Out] automaton2
) -> (Array[In] | nil)
104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 |
# File 'lib/lernen/automaton/transition_system.rb', line 104 def self.(alphabet, automaton1, automaton2) unless automaton2.is_a?(automaton1.class) raise ArgumentError, "Cannot find a separating word for different type automata" end queue = [] prefix_hash = {} initial_pair = [automaton1.initial_conf, automaton2.initial_conf] queue << initial_pair prefix_hash[initial_pair] = [] until queue.empty? conf1, conf2 = queue.shift prefix = prefix_hash[[conf1, conf2]] alphabet.each do |input| word = prefix + [input] output1, next_conf1 = automaton1.step(conf1, input) output2, next_conf2 = automaton2.step(conf2, input) return word if output1 != output2 # steep:ignore next_pair = [next_conf1, next_conf2] unless prefix_hash.include?(next_pair) queue << next_pair prefix_hash[next_pair] = word end end end nil end |
.random_transition_function(alphabet:, min_state_size: 5, max_state_size: 10, num_reachable_paths: 2, random: Random) ⇒ Object
Generates a transition function randomly.
To make a transition function connected, this method generates a transition function in the following mannar.
-
Decide a number of states within ‘min_state_size..max_state_size` randomly.
-
Divides the states into ‘num_reachable_paths` partitions.
-
Generate a path from the initial state for each paratition.
-
Generate transition for all ‘state` and `input`.
This method returns a pair of a transition function and an array of reachable paths. The initial state of the result transition function is ‘0`.
: [In] (
alphabet: Array[In],
?min_state_size: Integer,
?max_state_size: Integer,
?num_reachable_paths: Integer,
?random: Random,
) -> [Hash[[Integer, In], Integer], Array[Array[Integer]]]
158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 |
# File 'lib/lernen/automaton/transition_system.rb', line 158 def self.random_transition_function( alphabet:, min_state_size: 5, max_state_size: 10, num_reachable_paths: 2, random: Random ) state_size = random.rand(min_state_size..max_state_size) num_reachable_paths = [num_reachable_paths, alphabet.size, state_size].min #: Integer initial_state = 0 reachable_paths = [] transition_function = {} partitions = (0...state_size).to_a + ([nil] * (num_reachable_paths - 1)) partitions.shuffle!(random:) partitions.push(nil) initial_alphabet = alphabet.dup initial_alphabet.shuffle!(random:) until partitions.empty? reachable_path = [initial_state] state = initial_state input = initial_alphabet.shift loop do next_state = partitions.shift break if next_state.nil? next if next_state == initial_state reachable_path << next_state transition_function[[state, input]] = next_state input = alphabet.sample(random:) end reachable_paths << reachable_path end state_size.times do |state| alphabet.each do |input| next if transition_function[[state, input]] next_state = random.rand(state_size) transition_function[[state, input]] = next_state end end [transition_function, reachable_paths] end |
Instance Method Details
#initial_conf ⇒ Object
Returns the initial configuration.
This is an abstract method.
: () -> Conf
44 45 46 |
# File 'lib/lernen/automaton/transition_system.rb', line 44 def initial_conf raise TypeError, "abstract method: `initial_conf`" end |
#run(word) ⇒ Object
77 78 79 80 81 82 83 84 85 |
# File 'lib/lernen/automaton/transition_system.rb', line 77 def run(word) conf = initial_conf outputs = [] word.each do |input| output, conf = step(conf, input) outputs << output end [outputs, conf] end |
#step(conf, input) ⇒ Object
Runs a transition from the given configuration with the given input.
It returns a pair of the output value and the next configuration of this transition.
This is an abstract method.
: (Conf conf, In input) -> [Out, Conf]
56 57 58 |
# File 'lib/lernen/automaton/transition_system.rb', line 56 def step(conf, input) raise TypeError, "abstract method: `step`" end |
#to_dot ⇒ Object
Returns a [GraphViz](graphviz.org) DOT diagram of this transition system.
: () -> String
95 |
# File 'lib/lernen/automaton/transition_system.rb', line 95 def to_dot = to_graph.to_dot |
#to_graph ⇒ Object
Returns a graph of this transition system.
This is an abstract method.
: () -> Graph
65 66 67 |
# File 'lib/lernen/automaton/transition_system.rb', line 65 def to_graph raise TypeError, "abstract method: `to_graph`" end |
#to_mermaid(direction: "TD") ⇒ Object
Returns a [Mermaid](mermaid.js.org) diagram of this transition system.
: (?direction: Graph::mermaid_direction) -> String
90 |
# File 'lib/lernen/automaton/transition_system.rb', line 90 def to_mermaid(direction: "TD") = to_graph.to_mermaid(direction:) |
#type ⇒ Object
Returns the automaton type.
This is an abstract method.
: () -> transition_system_type
35 36 37 |
# File 'lib/lernen/automaton/transition_system.rb', line 35 def type raise TypeError, "abstract method: `type`" end |