Class: RLSM::DFA

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

Instance Attribute Summary collapse

Class Method Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(description) ⇒ DFA

Creates a new DFA. The description is a string which describes states and transitions. A state is described by a descriptor, which consists of latin letters and numbers (no whitespaces).

To indicate a final state, the state descriptor starts with a *. This is allowed multiple times, even for the same state.

The initial state starts with a right brace (‘}’). This is only allowed once.

A transition is described as follows

STATE -LETTERLIST-> STATE

were STATE is a state descriptor (* and } modifiers allowed) and LETTERLIST is either a single letter of the alphabet or a comma seperated list of alphabet letters.

Remark: This desription format may be the worst design desicion in the whole gem …

Example: RLSM::DFA RLSM::DFA[“}s1 s2 *s3 s1-a->s2 s2-a,b->*s3 s3-b->s1”] RLSM::DFA[“}s1 s2 *s3 }s1-a->s2 s2-a,b->*s3 s3-b->s1”] # => Error



33
34
35
36
37
38
 
# File 'lib/rlsm/dfa.rb', line 33

def initialize(description)
  parse_initial_state(description)
  parse_states(description)
  parse_final_states(description)
  parse_transitions(description)
end

Instance Attribute Details

#alphabet ⇒ Object (readonly)

The alphabet of the DFA.



50
51
52
 
# File 'lib/rlsm/dfa.rb', line 50

def alphabet
  @alphabet
end

#final_states ⇒ Object (readonly)

Array of accepting states.



44
45
46
 
# File 'lib/rlsm/dfa.rb', line 44

def final_states
  @final_states
end

#initial_state ⇒ Object (readonly)

Initial state of the DFA.



41
42
43
 
# File 'lib/rlsm/dfa.rb', line 41

def initial_state
  @initial_state
end

#states ⇒ Object (readonly)

Array of all states



47
48
49
 
# File 'lib/rlsm/dfa.rb', line 47

def states
  @states
end

Class Method Details

.[](description) ⇒ Object

Synonym for new.



12
13
14
 
# File 'lib/rlsm/dfa.rb', line 12

def self.[](description)
  new(description)
end

Instance Method Details

#<<(string) ⇒ Object

Processes given string starting in the initial state.



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

def <<(string)
  self[@initial_state, string]
end

#==(other) ⇒ Object

Checks for equality. A DFA is equal to other iff it has the same alphabet, states, final states, initial state and transitions.



160
161
162
163
164
165
166
167
168
169
170
 
# File 'lib/rlsm/dfa.rb', line 160

def ==(other)
  begin
    @alphabet == other.alphabet and
      @initial_state == other.initial_state and
      @states.sort == other.states.sort and
      @final_states.sort == other.final_states.sort and
      transitions.sort == other.transitions.sort
  rescue
    false
  end
end

#=~(other) ⇒ Object

Checks if self is isomorph to other.



218
219
220
221
222
223
224
225
226
227
228
229
230
 
# File 'lib/rlsm/dfa.rb', line 218

def =~(other)
  return false if other.class != self.class || 
    @alphabet != other.alphabet ||
    @states.size != other.states.size || 
    @final_states.size != other.final_states.size ||
    transitions.size != other.transitions.size

  bijective_maps_to(other).any? do |bijection|
    transitions.all? do |s1,s2,letter|
      other.transitions.include?([bijection[s1],bijection[s2],letter])
    end
  end
end

#[](state, string) ⇒ Object

Processes given string starting in state state.



67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
 
# File 'lib/rlsm/dfa.rb', line 67

def [](state, string)
  unless @states.include?(state)
    raise RLSM::Error, "Unknown state: #{state}"
  end

  present_state = state
  string.scan(/./).each do |letter|
    if @transitions[present_state].nil?
      return nil
    else
      present_state = @transitions[present_state][letter]
    end
  end

  present_state
end

#accepts?(string) ⇒ Boolean

Checks if this DFA accepts the given string, i.e. halts in a final state after processing the string.

Returns:

  • (Boolean) 


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

def accepts?(string)
  @final_states.include?( self << string )
end

#complete? ⇒ Boolean

Checks if DFA is complete, i.e. each state accepts every alphabet letter.

Returns:

  • (Boolean) 


116
117
118
119
120
121
122
 
# File 'lib/rlsm/dfa.rb', line 116

def complete?
  @states.all? do |state|
    @alphabet.all? do |letter| 
      self[state,letter]
    end
  end
end

#connected? ⇒ Boolean

Checks if each state is reachable. See reachable?.

Returns:

  • (Boolean) 


111
112
113
 
# File 'lib/rlsm/dfa.rb', line 111

def connected?
  @states.all? { |state| reachable?(state) }
end

#dead?(state) ⇒ Boolean

Checks if given state is dead, i.e. its not a final state and it hs no outgoing transitions.

Returns:

  • (Boolean)

Raises:



95
96
97
98
99
100
101
 
# File 'lib/rlsm/dfa.rb', line 95

def dead?(state)
  raise RLSM::Error, "Unknown state: #{state}" unless @states.include?(state)
  
  state != @initial_state and
    ! @final_states.include?(state) and
    @alphabet.all? { |let| [nil,state].include? @transitions[state][let] }
end

#equivalent_to(other) ⇒ Object

Checks if self is equivalent to other, i.e. they accepts the same language.



233
234
235
236
237
 
# File 'lib/rlsm/dfa.rb', line 233

def equivalent_to(other)
  return false if other.class != self.class

  minimize =~ other.minimize
end

#minimal? ⇒ Boolean

Checks if the DFA is minimal.

Returns:

  • (Boolean) 


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

def minimal?
  equivalent_state_pairs.empty?
end

#minimize ⇒ Object

Returns an equivalent minmal DFA.



213
214
215
 
# File 'lib/rlsm/dfa.rb', line 213

def minimize
  Marshal.load(Marshal.dump(self)).minimize!
end

#minimize! ⇒ Object

Alters the DFA in place to an equivalent minmal one.



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
207
208
209
210
 
# File 'lib/rlsm/dfa.rb', line 178

def minimize!
  remove_unneeded_states!

  unless minimal?
    state_classes = get_equivalent_state_classes
  
    states = state_classes.map { |cls| cls.min }

    rename = {}

    @states.each do |state|
      rename[state] = state_classes.find { |cls| cls.include?(state) }.min
    end

    transitions = {}

    @transitions.each_pair do |state, transition|
      start = (transitions[rename[state]] ||= {})

      transition.each_pair do |letter, destination|
        start[letter] = rename[destination]
      end
    end

    @initial_state = rename[@initial_state]
    @states = states
    @final_states.map! { |state| rename[state] }
    @final_states.uniq!
    @transitions = transitions
   end

  self
end

#reachable?(state) ⇒ Boolean

Checks if given state is reachable, i.e. it exists a string, such that self << string == state is true.

Returns:

  • (Boolean)

Raises:



104
105
106
107
108
 
# File 'lib/rlsm/dfa.rb', line 104

def reachable?(state)
  raise RLSM::Error, "Unknown state: #{state}" unless @states.include?(state)

  reachable_states.include? state
end

#to_dfa ⇒ Object

Simply returns self.



254
255
256
 
# File 'lib/rlsm/dfa.rb', line 254

def to_dfa
  self
end

#to_monoid ⇒ Object

Returns the transition monoid of the equivalent minimal DFA (which is in fact isomorph to the syntactic monoid of the represented language.



259
260
261
 
# File 'lib/rlsm/dfa.rb', line 259

def to_monoid
  minimize.transition_monoid
end

#to_regexp ⇒ Object

Calculates a regular expression which represents the same languge as the DFA.



240
241
242
243
244
245
246
247
248
249
250
251
 
# File 'lib/rlsm/dfa.rb', line 240

def to_regexp
  les = []
  les << initialize_row_for(@initial_state)
  (@states - [@initial_state]).each do |state|
    les << initialize_row_for(state)
  end

  #Solve for the initial state
  les = update_les(les, simplify_les_row(les.pop)) until les.size == 1

  simplify_les_row(les.pop)[:final]
end

#transition_monoid ⇒ Object

Calculates the transition monoid of the DFA.



125
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
155
156
157
 
# File 'lib/rlsm/dfa.rb', line 125

def transition_monoid
  maps = [@states.dup]
  elements = ['id']

  length = 1
  found_all_elements = false

  until found_all_elements
    words(length) do |word|
      found_all_elements = true
      
      map = get_map(word)
      unless maps.include?(map)
        maps << map
        elements << word
        found_all_elements = false
      end
    end

    length += 1
  end

  monoid_description = elements.join(',')

  elements[1..-1].each do |element|
    monoid_description += " #{element},"
    monoid_description += elements[1..-1].map do |element2|
      elements[maps.index(get_map(element+element2))]
    end.join(',')
  end

  RLSM::Monoid[ monoid_description ]
end

#transitions ⇒ Object

Returns array of transitions (a transition is a triple consisting of start, destination and label).



53
54
55
56
57
58
59
60
61
62
63
64
 
# File 'lib/rlsm/dfa.rb', line 53

def transitions
  return [] if @transitions.nil?

  result = []
  @transitions.each do |state,labels|
    labels.each do |label,dest|
      result << [state,dest,label]
    end
  end

  result
end