Class: Automaton

Inherits:
Object
  • Object
show all
Defined in:
lib/layout.rb,
lib/latex.rb,
lib/automaton.rb

Overview

Author

Tor Erik Linnerud ([email protected])

Author

Tom Gundersen ([email protected])

Copyright

Copyright © 2008 JKLM DA

License

MIT

Defined Under Namespace

Classes: Graph, Latex, Layout, Transition

Instance Attribute Summary collapse

Class Method Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(start, finals, graph) ⇒ Automaton

Create a new automaton. new is intended for internal use. create makes it easier to create an automaton from scratch. start - A symbol finals - A set of symbols graph - A transition function (Graph) which can be created like this:

Automaton.new(:a, Set[:c], Graph.from_hash(:a => {'1' => Set[:b]}, :b => {'2' => Set[:a, :c]}))

This is interpreted as an Automaton with start state a, final (accepting) states :c, a transition from :a to :b on the letter 1 and a transition from :b to :a and :c on the letter 2.

Raises:

  • (ArgumentError) 


23
24
25
26
27
28
29
 
# File 'lib/automaton.rb', line 23

def initialize(start, finals, graph)
  raise ArgumentError, 'Invalid transition function' unless graph.is_a?(Graph)
  @start = start 
  @finals = finals
  @graph = graph
  @alphabet = graph.values.map{|transitions| transitions.keys}.flatten.to_set
end

Instance Attribute Details

#alphabet ⇒ Object (readonly)

Returns the value of attribute alphabet.



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

def alphabet
  @alphabet
end

#finals ⇒ Object (readonly)

Returns the value of attribute finals.



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

def finals
  @finals
end

#graph ⇒ Object (readonly)

Returns the value of attribute graph.



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

def graph
  @graph
end

#start ⇒ Object (readonly)

Returns the value of attribute start.



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

def start
  @start
end

Class Method Details

.create(start, finals, graph) ⇒ Object

Create a new automaton, intended for public use Unlike new, create allows you to use a single element instead of an array when you just have a single element. Furthermore, graph can be (and must be) a hash, instead of a Graph. Instead of

Automaton.new(:a, Set[:c], Graph.from_hash(:a => {'1' => [:b]}, :b => {'2' => [:a, :c]}))

you can now simply do

Automaton.create(:a, :c, :a => {'1' => :b}, :b => {'2' => :c})

Raises:

  • (ArgumentError) 


38
39
40
41
42
43
44
 
# File 'lib/automaton.rb', line 38

def self.create(start, finals, graph)
  raise ArgumentError, "finals shouldn't be passed to create as a set" if finals.is_a?(Set)
  nfa_graph = graph.value_map do |state, transitions|
    transitions.value_map {|symbol, s| [s].flatten}
  end
  self.new(start, [finals].flatten.to_set, Graph.from_hash(nfa_graph)).prune
end

Instance Method Details

#-(other) ⇒ Object

Automaton accepting the language accepted by self minus the language accepted by other



113
114
115
116
 
# File 'lib/automaton.rb', line 113

def -(other)
  alphabet = self.alphabet + other.alphabet
  self.intersect(other.to_total(alphabet).complement)
end

#==(other) ⇒ Object 



90
91
92
93
94
 
# File 'lib/automaton.rb', line 90

def ==(other)
  start == other.start &&
    finals == other.finals &&
    graph == other.graph
end

#accepting? ⇒ Boolean

Will the Automaton accept any string at all?

Returns:

  • (Boolean) 


74
75
76
 
# File 'lib/automaton.rb', line 74

def accepting?
  !(reachable_states & finals).empty?
end

#accepting_same_language_as?(other) ⇒ Boolean

self.language == other.language?

Returns:

  • (Boolean) 


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

def accepting_same_language_as?(other)
  self.subset?(other) &&
    other.subset?(self)
end

#complement ⇒ Object

Automaton accepting the complement of the language accepted by self



55
56
57
 
# File 'lib/automaton.rb', line 55

def complement
  self.class.new(start, reachable_states - finals, graph)
end

#intersect(other) ⇒ Object

Create the intersection of two automata, which is basically the cartesian product of the two



97
98
99
100
101
102
103
104
105
106
107
108
109
110
 
# File 'lib/automaton.rb', line 97

def intersect(other)
  start = self.start + other.start
  finals = self.finals.to_a.product(other.finals.to_a).map{|a,b| a + b}.to_set
  product = self.graph.product(other.graph)
  graph = product.key_value_map do |(state1, state2), (transitions1, transitions2)|
    common_symbols = transitions1.keys & transitions2.keys
    transitions = common_symbols.map do |symbol|
      states = transitions1[symbol].to_a.product(transitions2[symbol].to_a).map{|a, b| a + b}
      [symbol, states]
    end.to_h
    [state1 + state2, transitions]
  end
  self.class.new(start, finals, graph).prune
end

#prune ⇒ Object

Keep only reachable states. (Removes all unreachable states.)



47
48
49
50
51
52
 
# File 'lib/automaton.rb', line 47

def prune
  reachable_states_cache = reachable_states
  finals = self.finals & reachable_states_cache
  graph = self.graph.prune(reachable_states_cache)
  self.class.new(start, finals, graph)
end

#reachable_states(from = start, already_seen = Set.new) ⇒ Object

States reachable from the start state (default), or any other given state



60
61
62
63
64
 
# File 'lib/automaton.rb', line 60

def reachable_states(from = start, already_seen = Set.new)
  new_states = (successors_of(from) - already_seen - [from])
  already_seen = already_seen + new_states + [from]
  new_states.inject(Set.new){|reachables, state| reachables + reachable_states(state, already_seen)} + [from]
end

#subset?(other) ⇒ Boolean

self.language subset of other.language?

Returns:

  • (Boolean) 


119
120
121
 
# File 'lib/automaton.rb', line 119

def subset?(other)
  !(self - other).accepting?
end

#successors_of(state) ⇒ Object

States reachable from state in one sucession



67
68
69
70
71
 
# File 'lib/automaton.rb', line 67

def successors_of(state)
  state_transitions = graph[state]
  return [] unless state_transitions
  state_transitions.values.inject(Set.new){|reachables, states| reachables + states}
end

#tag(name) ⇒ Object

New automaton with each state tagged with the given name



79
80
81
82
83
84
85
86
87
88
 
# File 'lib/automaton.rb', line 79

def tag(name)
  tagged_finals = finals.map{|state| state.tag(name)}.to_set
  tagged_graph = graph.key_value_map  do |state, transitions|
    tagged_transitions = transitions.value_map do |symbol, states|
      states.map{|s| s.tag(name)}.to_set
    end
    [state.tag(name), tagged_transitions]
  end
  self.class.new(start.tag(name), tagged_finals, tagged_graph)
end

#to_tex ⇒ Object

Image of the Automaton in the form of a string of latex



153
154
155
156
157
158
159
160
161
162
163
164
165
 
# File 'lib/automaton.rb', line 153

def to_tex
  nodes = reachable_states.each_with_index.map{|state, i| [state, Layout::Node.new(state, rand * i , rand * i)]}.to_h
  transitions.each do |transition|
      nodes[transition.from].connect(nodes[transition.to])
  end
  nodes.values.each do |node|
    node.position *= 2.5
  end
  layout = Layout.new(*nodes.values)
  layout.force_direct
  layout.normalize
  Latex.new(start, finals, nodes.values, transitions)
end

#to_total(alphabet) ⇒ Object

New automaton which is the total version of self. This means that all states have a transition for every symbol in the alphabet.

Raises:

  • (ArgumentError) 


141
142
143
144
145
146
147
148
149
150
 
# File 'lib/automaton.rb', line 141

def to_total(alphabet)
  raise ArgumentError unless alphabet.is_a?(Set)
  all_states = Graph.from_hash((reachable_states + [:x]).map{|state| [state, {}]}.to_h)
  total_graph = all_states.merge(graph).value_map do |state, transitions|
    missing_symbols = (alphabet - transitions.keys.to_set)
    missing_transitions = missing_symbols.map{|symbol| [symbol, [:x]]}.to_h
    transitions.merge(missing_transitions)
  end
  self.class.new(start, finals, total_graph).prune
end

#transitions ⇒ Object

Set of transitions in the Automaton



130
131
132
133
134
135
136
137
138
 
# File 'lib/automaton.rb', line 130

def transitions
  graph.map do |from, transitions|
    transitions.map do |label, to|
      to.map do |to|
        Transition.new(from, to, label)
      end
    end
  end.flatten
end