Class: Lernen::Automaton::DFA

Inherits:
MooreLike show all
Defined in:
lib/lernen/automaton/dfa.rb

Overview

DFA represents a [deterministic finite-state automaton](en.wikipedia.org/wiki/Deterministic_finite_automaton).

Instance Attribute Summary collapse

Class Method Summary collapse

Instance Method Summary collapse

Methods inherited from MooreLike

find_separating_word, #run_empty, #step

Methods inherited from TransitionSystem

find_separating_word, random_transition_function, #run, #step, #to_dot, #to_mermaid

Constructor Details

#initialize(initial_state, accept_state_set, transition_function) ⇒ DFA

: (

  Integer initial_state,
  Set[Integer] accept_state_set,
  Hash[[Integer, In], Integer] transition_function
) -> void



19
20
21
22
23
24
25
 
# File 'lib/lernen/automaton/dfa.rb', line 19

def initialize(initial_state, accept_state_set, transition_function)
  super()

  @initial_state = initial_state
  @accept_state_set = accept_state_set
  @transition_function = transition_function
end

Instance Attribute Details

#accept_state_set ⇒ Object (readonly)

: Set



28
29
30
 
# File 'lib/lernen/automaton/dfa.rb', line 28

def accept_state_set
  @accept_state_set
end

#initial_state ⇒ Object (readonly)

: Integer



27
28
29
 
# File 'lib/lernen/automaton/dfa.rb', line 27

def initial_state
  @initial_state
end

#transition_function ⇒ Object (readonly)

: Hash[[Integer, In], Integer]



29
30
31
 
# File 'lib/lernen/automaton/dfa.rb', line 29

def transition_function
  @transition_function
end

Class Method Details

.random(alphabet:, min_state_size: 5, max_state_size: 10, accept_state_size: 2, random: Random) ⇒ Object

Generates a DFA randomly.

: [In] (

  alphabet: Array[In],
  ?min_state_size: Integer,
  ?max_state_size: Integer,
  ?accept_state_size: Integer,
  ?random: Random,
) -> DFA[In]



189
190
191
192
193
194
195
196
197
198
199
200
201
 
# File 'lib/lernen/automaton/dfa.rb', line 189

def self.random(alphabet:, min_state_size: 5, max_state_size: 10, accept_state_size: 2, random: Random)
  transition_function, reachable_paths =
    TransitionSystem.random_transition_function(
      alphabet:,
      min_state_size:,
      max_state_size:,
      num_reachable_paths: accept_state_size,
      random:
    )
  accept_state_set = reachable_paths.to_set(&:last) #: Set[Integer]

  new(0, accept_state_set, transition_function)
end

Instance Method Details

#==(other) ⇒ Object

Checks the structural equality between ‘self` and `other`.

: (untyped other) -> bool



46
47
48
49
 
# File 'lib/lernen/automaton/dfa.rb', line 46

def ==(other)
  other.is_a?(DFA) && initial_state == other.initial_state && accept_state_set == other.accept_state_set &&
    transition_function == other.transition_function
end

#compute_shortest_words(alphabet) ⇒ Object

Computes the shortest paths between states.

: (Array alphabet) -> Hash[[Integer, Integer], Array]



126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
 
# File 'lib/lernen/automaton/dfa.rb', line 126

def compute_shortest_words(alphabet)
  states = states()

  shortest_words = {}

  states.each do |state|
    alphabet.each do |input|
      next_state = transition_function[[state, input]]
      shortest_words[[state, next_state]] = [input]
    end

    shortest_words[[state, state]] = []
  end

  states.each do |state2|
    states.each do |state1|
      states.each do |state3|
        word12 = shortest_words[[state1, state2]]
        word23 = shortest_words[[state2, state3]]
        word13 = shortest_words[[state1, state3]]
        next unless word12 && word23

        shortest_words[[state1, state3]] = word12 + word23 if !word13 || word12.size + word23.size < word13.size
      end
    end
  end

  shortest_words
end

#error_state ⇒ Object

Returns the error state of this DFA.

An error state is:

  • neither a initial state nor accepting states, and

  • only having self-loops for all ‘input`.

If an error state is not found, it returns ‘nil`.

: () -> (Integer | nil)



77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
 
# File 'lib/lernen/automaton/dfa.rb', line 77

def error_state
  transition_function
    .group_by { |(state, _), _| state }
    .transform_values { _1.to_h { |(_, input), next_state| [input, next_state] } }
    .each do |state, transition_hash|
      # The initial state and accepting states are not an error state.
      next if state == initial_state || accept_state_set.include?(state)

      # An error state should only have self-loops.
      next unless transition_hash.all? { |_, next_state| state == next_state }

      return state
    end

  nil
end

#initial_conf ⇒ Object 



35
 
# File 'lib/lernen/automaton/dfa.rb', line 35

def initial_conf = initial_state

#output(conf) ⇒ Object 



41
 
# File 'lib/lernen/automaton/dfa.rb', line 41

def output(conf) = accept_state_set.include?(conf)

#shortest_accept_word(alphabet) ⇒ Object

Returns the shortest word accepted by this DFA.

If it is not found, it returns ‘nil`.

: (Array alphabet) -> (Array | nil)



99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
 
# File 'lib/lernen/automaton/dfa.rb', line 99

def shortest_accept_word(alphabet)
  return [] if accept_state_set.include?(initial_state)

  visited = Set.new
  queue = []

  visited << initial_state
  queue << [initial_state, []]

  until queue.empty?
    state, word = queue.shift
    alphabet.each do |input|
      next_state = transition_function[[state, input]]
      return word + [input] if accept_state_set.include?(next_state)
      unless visited.include?(next_state)
        visited << next_state
        queue << [next_state, word + [input]]
      end
    end
  end

  nil
end

#states ⇒ Object

Returns the array of states of this DFA.

The result array is sorted.

: () -> Array



56
57
58
59
60
61
62
63
64
65
 
# File 'lib/lernen/automaton/dfa.rb', line 56

def states
  state_set = Set.new
  state_set << initial_state
  accept_state_set.each { |state| state_set << state }
  transition_function.each do |(state, _), next_state|
    state_set << state
    state_set << next_state
  end
  state_set.to_a.sort!
end

#step_conf(conf, input) ⇒ Object 



38
 
# File 'lib/lernen/automaton/dfa.rb', line 38

def step_conf(conf, input) = transition_function[[conf, input]]

#to_graph(shows_error_state: false) ⇒ Object

Returns a graph of this DFA.

(?shows_error_state: bool) -> Graph



159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
 
# File 'lib/lernen/automaton/dfa.rb', line 159

def to_graph(shows_error_state: false)
  error_state = error_state() unless shows_error_state

  nodes =
    states
      .filter_map do |state|
        next if state == error_state
        shape = accept_state_set.include?(state) ? :doublecircle : :circle #: Graph::node_shape
        [state, Graph::Node[state.to_s, shape]]
      end
      .to_h

  edges =
    transition_function.filter_map do |(state, input), next_state|
      next if state == error_state || next_state == error_state
      Graph::Edge[state, input.inspect, next_state] # steep:ignore
    end

  Graph.new(nodes, edges)
end

#type ⇒ Object

: () -> :dfa



32
 
# File 'lib/lernen/automaton/dfa.rb', line 32

def type = :dfa