Class: RLSM::DFA

Inherits:
Object show all
Defined in:
lib/dfa.rb

Defined Under Namespace

Classes: State

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(alph, states, initial, finals, transitions) ⇒ DFA

Returns a new instance of DFA.



25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
 
# File 'lib/dfa.rb', line 25

def initialize(alph, states, initial, finals, transitions)
  @alphabet = alph.sort

  #State identifiers should be unique and shouldn't be trap
  if states.uniq != states or states.include? 'trap'
    raise Exception, "Bad states. State names must be unique and not 'trap'"
  end

  #Create the states
  @states = states.map do |state|
    if state == initial
      if finals.include? state
        State.new(self, state.to_s, :initial => true, :final => true)
      else
        State.new(self, state.to_s, :initial => true)
      end
    elsif finals.include? state
      State.new(self, state.to_s, :final => true)
    else
      State.new(self, state.to_s)
    end
  end
  
  #Add the transitions and check for completness
  @states.each do |state|
    transitions.select { |c, s1, s2| s1.to_s == state.label }.each do |c, s1, s2|
      state.add_transition c, _get_state(s2.to_s)
    end
  end
  
  #Calculate the reachable states
  @reachable_states = [initial_state]
  changed = true
  
  while changed
    changed = false
    (@states - @reachable_states).each do |state|
      if @reachable_states.any? { |s| s.reachable_states.include? state }
        @reachable_states << state
        changed = true
      end
    end
  end

  #Bring the initial state to index 0
  ii = @states.index(initial_state)
  if ii != 0
    @states[0], @states[ii] = @states[ii], @states[0]
  end
end

Instance Attribute Details

#alphabet ⇒ Object (readonly)

Returns the value of attribute alphabet.



76
77
78
 
# File 'lib/dfa.rb', line 76

def alphabet
  @alphabet
end

#reachable_states ⇒ Object (readonly)

Returns the value of attribute reachable_states.



76
77
78
 
# File 'lib/dfa.rb', line 76

def reachable_states
  @reachable_states
end

Instance Method Details

#==(other) ⇒ Object

A synonym for isomorph_to?



172
173
174
 
# File 'lib/dfa.rb', line 172

def ==(other)
  isomorph_to? other
end

#accepts?(str) ⇒ Boolean

Returns true if the given string is accepted by the DFA.

Returns:

  • (Boolean) 


115
116
117
118
119
 
# File 'lib/dfa.rb', line 115

def accepts?(str)
  s = process(str)
  #Full String parsed, are we now in a final state or was an error?
  s ? s.final? : false
end

#complete ⇒ Object

Returns a complete DFA which accepts the same language.



312
313
314
 
# File 'lib/dfa.rb', line 312

def complete
  self.deep_copy.complete!
end

#complete! ⇒ Object

Adds a dead state and adds to every other state a transition to this state for all missing alphabet elements. If the DFA is already complete nothing happens.

In either case the complete DFA is returned.



319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
 
# File 'lib/dfa.rb', line 319

def complete!
  #Is work to do?
  return self if complete?

  #Create the trap state
  trap = State.new(self, 'trap')
  @alphabet.each do |char|
    trap.add_transition char, trap
  end
  
  #Add the necassery transitions
  @states.each do |state|
    unless state.complete?
      (@alphabet - state.accepted_chars).each do |char|
        state.add_transition char, trap
      end
    end
  end
  
  #Add the trap state to the DFA
  @states << trap
  @reachable_states << trap

  self
end

#complete? ⇒ Boolean

Returns true if this DFA is complete, i.e. all states accepts all alphabet symbols.

Returns:

  • (Boolean) 


346
347
348
349
350
 
# File 'lib/dfa.rb', line 346

def complete?
  @states.all? do |state|
    state.complete?
  end
end

#dead_states ⇒ Object

Returns an array of dead states (a state is dead, if it is not final and has outdegree 0)



353
354
355
 
# File 'lib/dfa.rb', line 353

def dead_states
  @states.find_all { |state| state.dead? }
end

#dead_states? ⇒ Boolean

Returns true if the DFA has dead states (see also dead_states)

Returns:

  • (Boolean) 


358
359
360
 
# File 'lib/dfa.rb', line 358

def dead_states?
  @states.find { |state| state.dead? } ? true : false
end

#equivalent_to?(other) ⇒ Boolean

Returns true, if the two DFAs accepts the same language, i.e. the mimimized DFAs are isomorph.

Returns:

  • (Boolean) 


177
178
179
 
# File 'lib/dfa.rb', line 177

def equivalent_to?(other)
  minimze == other.minimize
end

#final_states ⇒ Object

Returns an array of all final states.



84
85
86
 
# File 'lib/dfa.rb', line 84

def final_states
  @finals ||= @states.find_all { |state| state.final? }.deep_copy
end

#initial_state ⇒ Object

Returns the initial state



79
80
81
 
# File 'lib/dfa.rb', line 79

def initial_state
  @initial ||= @states.find { |state| state.initial? }.deep_copy
end

#isomorph_to?(other) ⇒ Boolean

Returns true if a DFA isomorphism between self and other exists.

Returns:

  • (Boolean) 


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
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
 
# File 'lib/dfa.rb', line 129

def isomorph_to?(other)
  #First a few necessary conditions
  return false if num_states != other.num_states
  return false if num_finals != other.num_finals
  return false if alphabet != other.alphabet

  initial_index = @states.index(initial_state)
  final_indices = final_states.map { |f| @states.index(f) }
  (0...num_states).to_a.permutations.each do |per|
    #Initial state must map to initial state
    next unless other.states[per[initial_index]].initial?

    #Finals must map to finals
    next unless final_indices.all? { |fi| other.states[fi].final? }

    #Transactions respected?
    bad = @states.find do |state|
      not @alphabet.all? do |char|
        si = @states.index(state)
        ps = state.process(char)

        if ps.nil?
          other.states[per[si]].process(char).nil?
        else
          os = other.states[per[si]].process(char)
          if os.nil?
            false
          else
            per[@states.index(ps)] == other.states.index(os)
          end
        end
      end
    end

    #Found an iso, i.e. no bad states?
    return true unless bad
  end

  #No isomorphism found
  return false
end

#minimal? ⇒ Boolean

Returns true if the DFA is minimal (see minimize!).

Returns:

  • (Boolean) 


307
308
309
 
# File 'lib/dfa.rb', line 307

def minimal?
  num_states == minimize.num_states
end

#minimize(opts = {}) ⇒ Object

Returns a minimal DFA which accepts the same language (see minimize!)



220
221
222
 
# File 'lib/dfa.rb', line 220

def minimize(opts = {})
  self.deep_copy.minimize!(opts)
end

#minimize!(opts = {}) ⇒ Object

If passed :rename_states => true, the state labels will be renamed to something short (propably 0,1,2,…).



227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
 
# File 'lib/dfa.rb', line 227

def minimize!(opts = {})
  #First step: remove unreachable states
  remove_unreachable_states!

  complete_temp = complete?

  #Second step: Find all equivalent states
  #Create the initial state partition
  sp = @states.partition { |state| state.final? }
  sp_labels = sp.map { |sc| sc.map {|st| st.label} }.sort
  
  #Calculate the new state partition for the first time
  nsp = new_state_partition(sp)
  nsp_labels = nsp.map { |sc| sc.map {|st| st.label} }.sort
  
  #Find all state classes (repeating process until nothing changes)
  while sp_labels != nsp_labels
    sp, nsp = nsp.deep_copy, new_state_partition(nsp)
    
    sp_labels = sp.map { |sc| sc.map {|st| st.label} }.sort
    nsp_labels = nsp.map { |sc| sc.map {|st| st.label} }.sort
  end

  #Third step: Are we done?
  #Check if the DFA was already minimal
  return self if sp.all? { |sc| sc.size == 1 }
  
  #Fourth step: Constructing the new DFA:
  #1 the states
  @states = sp.map do |sc|
    state_label = sc.map { |s| s.label }.join
    if sc.include? initial_state
      if final_states.any? {|f| sc.include? f }
        State.new(self, state_label, :initial => true, :final => true)
      else
        State.new(self, state_label, :initial => true)
      end
    elsif final_states.any? { |f| sc.include? f }
      State.new(self, state_label, :final => true)
    else
      State.new(self, state_label)
    end
  end

  #2 the transitions
  @states.each_with_index do |state, sc_index|
    sp[sc_index].first.transitions.each_pair do |char, s2|
      state.add_transition char, @states[_class_index_of(sp,s2)]
    end
  end
  
  
  #3 delete dead states
  remove_dead_states!(:except_trap => complete_temp)

  #4 Force recalculation of initial and final states
  @initial, @finals = nil, nil

  #Bring the initial state to index 0
  ii = @states.index(initial_state)
  if ii != 0
    @states[0], @states[ii] = @states[ii], @states[0]
  end


  #5 Was renaming of the states requested?
  if opts[:rename_states]
    @states.each_with_index do |state,index|
      state.label = index.to_s
    end
  end

  #6 update the reachable states (all are reachable in a minimal DFA)
  @reachable_states = @states.deep_copy


  self
end

#num_finals ⇒ Object

The number of final states.



99
100
101
 
# File 'lib/dfa.rb', line 99

def num_finals
  final_states.size
end

#num_states ⇒ Object

The number of states



94
95
96
 
# File 'lib/dfa.rb', line 94

def num_states
  @states.size
end

#process(str, state = nil) ⇒ Object

Returns the state in which the DFA halts if started in state and given str. Returns nil if this string isn’t parseable by the DFA started in state. If the state is omitted, default start state is the initial state (surprising, isn’t it).



104
105
106
107
108
109
110
111
112
 
# File 'lib/dfa.rb', line 104

def process(str, state = nil)
  s = state || initial_state
  str.each_char do |char|
    s = s.process(char)
    return nil if s.nil?
  end

  s
end

#remove_dead_states(opt = {}) ⇒ Object

Returns a copy with dead states removed.



385
386
387
 
# File 'lib/dfa.rb', line 385

def remove_dead_states(opt = {})
  self.deep_copy.remove_dead_states!(opt)
end

#remove_dead_states!(opt = {}) ⇒ Object

Removes all dead_states. If passed :except_trap => true, trap states wouldn’t be removed.



363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
 
# File 'lib/dfa.rb', line 363

def remove_dead_states!(opt = {})
  @states.each do |state|
    state.remove_transitions_to_dead_states(opt)
  end

  #Remove the states
  if opt[:except_trap]
    @states = @states.reject do |state| 
      state.dead? and not state.trap? 
    end
    @reachable_states = @reachable_states.reject do |state| 
      state.dead? and not state.trap?
    end
  else
    @states = @states.reject { |state| state.dead? }
    @reachable_states = @reachable_states.reject { |state| state.dead? }
  end

  self
end

#remove_unreachable_states ⇒ Object

Returns a copy with unreachable states removed.



409
410
411
 
# File 'lib/dfa.rb', line 409

def remove_unreachable_states
  self.deep_copy.remove_unreachable_states!
end

#remove_unreachable_states! ⇒ Object

Removes all unreachable states.



400
401
402
403
404
405
406
 
# File 'lib/dfa.rb', line 400

def remove_unreachable_states!
  #No transition update necessary, because each state which reaches an unreachble state must be unreachable.
  @states = @states.reject { |state| state.unreachable? }
  @reachable_states = @states.deep_copy

  self
end

#similar_to?(other) ⇒ Boolean

Returns true, if the two DFAs accepts languages of the same structure, i.e. if the languages differs only in the used alphabet. For example the languages aab and bba are similar.

Returns:

  • (Boolean) 


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
207
208
209
210
211
212
213
214
215
216
217
 
# File 'lib/dfa.rb', line 182

def similar_to?(other)
  dfa1 = minimize
  dfa2 = other.minimize

  #First a few necessary conditions
  return false if dfa1.num_states != dfa2.num_states
  return false if dfa1.num_finals != dfa2.num_finals

  dfa1.alphabet.permutations do |per|
    #Get the states
    states = other.states.map { |st| st.label }

    #Get the initial
    initial = other.initial_state.label
    
    #Get the finals
    finals = other.final_states.map { |fs| fs.label }

    #Get the transitions
    trans = []
    other.states.each do |s| 
      s.transitions.each_pair { |c,os| trans << [c,s.label, os.label].dup }
    end

    #Alter the transitions wrt to the permutation
    trans.map! do |c,s1,s2|
      [per[other.alphabet.index(c)],s1,s2]
    end

    #Exisits now an isomorphism between self and the new dfa?
    return true if self == new(@alphabet, states, initial, finals, trans)
  end

  #No similarity found
  return false
end

#states ⇒ Object

Returns an array of all states.



89
90
91
 
# File 'lib/dfa.rb', line 89

def states
  @states.deep_copy
end

#syntactic_monoid ⇒ Object

Returns the syntactic monoid which belongs to the language accepted by the DFA. (In fact, the transition monoid of the minimal DFA is returned, both monoids are isomorph)



501
502
503
 
# File 'lib/dfa.rb', line 501

def syntactic_monoid
  minimize.transition_monoid
end

#to_regexp ⇒ Object

Returns an RLSM::RegExp instance representing the same language as this DFA.



414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
 
# File 'lib/dfa.rb', line 414

def to_regexp
  #No finals => no language
  return RLSM::RegExp.new if final_states.empty?

  #Calculate the coeffizients matrix
  #1 empty matrix with lambdas for final states
  matr = @states.map do |st|
    last = st.final? ? [RLSM::RegExp.new('&')] : [RLSM::RegExp.new]
    [RLSM::RegExp.new]*num_states + last
  end

  #2 remaining coeffizients
  @states.each_with_index do |state,i|
    state.transitions.each_pair do |ch, st|
      matr[i][@states.index(st)] += RLSM::RegExp.new(ch)
    end
  end

  #Solve the matrix for matr[0][0] (Remember 0 is index of initial state)
  (num_states-1).downto 1 do |i|
    #Depends Ri on itself? If so apply well known simplify rule
    # R = AR +B -> R = A*B
    unless matr[i][i].empty?
      matr[i].map! { |re| matr[i][i].star * re }
      matr[i][i] = RLSM::RegExp.new
    end

    #Substitute know Ri in everey row above
    ri = matr.pop

    matr.map! do |row|
      row.each_with_index do |re,j|
        row[j] = re + ri[j]
      end

      row[i] = RLSM::RegExp.new

      row
    end
  end

  #Examine now the last remaining first row (irritating...)
  regexp = matr.pop

  if regexp[0].empty?  #R0 depends not on R0
    return regexp.last
  else                 #R0 depends on R0
    return regexp[0].star * regexp.last
  end
end

#to_s ⇒ Object

Returns a string represantation



506
507
508
 
# File 'lib/dfa.rb', line 506

def to_s
  @states.map { |state| state.to_s }.join("\n")
end

#transition_function(str) ⇒ Object

Caution: If a state can’t process str, for this state nil is returned. In a complete DFA for any valid input string, a non nil State will be returnd.



124
125
126
 
# File 'lib/dfa.rb', line 124

def transition_function(str)
  @states.map { |state| process(str, state) }
end

#transition_monoid ⇒ Object

Calculate the transition monoid of the DFA. Because it is only possible for an complete DFA to compute the TM, the TM is calculated for the DFA returned by complete.



466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
 
# File 'lib/dfa.rb', line 466

def transition_monoid
  dfa = self.complete

  #Calculate the monoid elements
  trans_tab = [["", dfa.transition_function("")]]
  
  new_elements = true
  str_length = 1
  while new_elements
    new_elements = false
    dfa.each_str_with_length(str_length) do |str|
      tf = dfa.transition_function(str)
      unless trans_tab.map { |s,f| f}.include? tf
        trans_tab << [str, tf]
        new_elements = true
      end
    end
    str_length += 1
  end
 
  #Calculate the binary operation
  binop = [(0...trans_tab.size).to_a]

  (1...trans_tab.size).each do |i|
    str = trans_tab[i].first
    binop << trans_tab.map do |s, tf|
      trans_tab.map {|st,f| f }.index(dfa.transition_function(str + s))
    end
  end

  
  RLSM::Monoid.new binop.map { |row| row.join(',') }.join(' ')      
end

#unreachable_states ⇒ Object

Returns an array of states, wich aren’t reachable from the initial state.



390
391
392
 
# File 'lib/dfa.rb', line 390

def unreachable_states
  @states.find_all { |state| state.unreachable?}
end

#unreachable_states? ⇒ Boolean

Returns true if the DFA has unreachable states

Returns:

  • (Boolean) 


395
396
397
 
# File 'lib/dfa.rb', line 395

def unreachable_states?
  @states.find { |state| state.unreachable? } ? true : false
end