class Fae::FiniteAutomata

The main class that drives the Finite Automata evaluation.

Takes in a language, states, and strings, and checks them to validate a state diagram.

Attributes

description[R]
language[R]
states[R]
strings[R]
valid_block[RW]

Public Class Methods

new(language, description) click to toggle source

Initializes a new instance of the FiniteAutomata.

@param language [Language] a language instance @param description [String] the description of the finite automata

# File lib/fae/finite_automata.rb, line 15
def initialize(language, description)
  @states = []
  @strings = []
  @invalids = []
  @language = language
  @description = description
end

Public Instance Methods

add_state(new_state) click to toggle source

Adds a single state to the states array.

@param new_state [State] the state to add.

# File lib/fae/finite_automata.rb, line 49
def add_state(new_state)
  valid = true
  @states.each do |state|
    raise Fae::DuplicateStateException, 'Duplicate state added for Finite Automata' if new_state.name == state.name
  end
  @states << new_state
end
add_states(states) click to toggle source

Adds strings to check against when evaluating.

@param states [Array] an array of states

# File lib/fae/finite_automata.rb, line 41
def add_states(states)
  states.each { |state| add_state(state) }
  self
end
add_string(string) click to toggle source

Adds a single string to the strings array.

@param string [String] the string to add

# File lib/fae/finite_automata.rb, line 34
def add_string(string)
  @strings << string
end
add_strings(strings) click to toggle source

Adds strings to check against when evaluating.

@param strings [Array] an array of strings

# File lib/fae/finite_automata.rb, line 26
def add_strings(strings)
  strings.each { |string| @strings << string }
  self
end
difference(fa) click to toggle source

Generates the finite automata for the difference of two different finite automatas.

@param fa [FiniteAutomata] the finite automata to difference this one with

# File lib/fae/finite_automata.rb, line 94
def difference(fa)
  perform_set_operation(:difference, fa)
end
evaluate!(suppress_output=false) click to toggle source

Runs the evaluation on the finite automata.

# File lib/fae/finite_automata.rb, line 99
def evaluate!(suppress_output=false)
  raise Fae::EmptyStatesException, 'You must add some states to your Finite Automata before checking strings' if @states.length == 0

  output = "Evaluating strings for #{@description} using language #{@language.characters}".colorize(:yellow)
  @invalids = []

  @strings.each do |string|
    result = evaluate_string(string)
    @invalids << string if !result[:valid]
    output    << result[:output]
  end

  num_invalid = @invalids.length
  valid = num_invalid == 0
  if !valid
    output << "\nState diagram may be incorrect for #{@description}\n".colorize(:red)
    output << "\nA total of #{num_invalid} string#{'s' if num_invalid != 1} did not meet your expectations:\n\n"

    @invalids.each do |string|
      expected_string = string.expected ? "valid".colorize(:green) : "invalid".colorize(:red)
      output << "* You expected the string '#{string.colorize(:blue)}' to be #{expected_string}\n"
    end
    output << "\nIf these expectations are correct, then your state diagram needs revising. Otherwise, you've simply expected the wrong values."
  else
    output << "\nState diagram is correct.\n".colorize(:green)
  end

  if (!suppress_output)
    puts output
  end
  valid
end
generate_strings(number, length) click to toggle source

Generates strings for the finite automata and adds them to the strings array.

@param number [Integer] number of strings @param length [Integer] length of each string

# File lib/fae/finite_automata.rb, line 137
def generate_strings(number, length)
  raise Fae::MissingValidBlockException, 'You must set the valid block for the Finite Automata to generate strings' if valid_block.nil?
  
  strings = []
  number.times do
    string = ""
    length.times { string << @language.characters.sample }
    strings << String.new(string, valid_block.call(string))
  end
  self.add_strings(strings)
  self
end
get_state(name) click to toggle source

Retrieves a state from this finite automata by name.

@param name [String] the name of the state to find

# File lib/fae/finite_automata.rb, line 60
def get_state(name)
  retrieved_state = nil
  @states.each do |state|
    if (state.name == name)
      retrieved_state = state
      break
    end
  end
  if (retrieved_state.nil?)
    raise Fae::StateNotFoundException, "State #{name} was not found in this Finite Automata. Ensure that all states have outputs for #{@language.characters}"
  end
  retrieved_state
end
intersection(fa) click to toggle source

Generates the finite automata for the intersection of two different finite automatas.

@param fa [FiniteAutomata] the finite automata to intersect this one with

# File lib/fae/finite_automata.rb, line 78
def intersection(fa)
  perform_set_operation(:intersection, fa)
end
to_s() click to toggle source
# File lib/fae/finite_automata.rb, line 150
def to_s
  output =  "Description: ".colorize(:yellow) + @description
  output << "\nLanguage: ".colorize(:yellow) + language.characters.to_s
  output << "\nStates:".colorize(:yellow)
  @states.each do |state|
    output << "\n  State #{state.name}: ".colorize(:blue)
    state.paths.keys.each do |key|
      output << "\n    #{'~'.colorize(:yellow)} #{key} #{'->'.colorize(:light_black)} #{state.paths[key]}"
    end
    accepting = state.accepting ? "accepting".colorize(:green) : "not accepting".colorize(:red)
    output << "\n    #{'~'.colorize(:yellow)} #{accepting}"
  end
  output
end
union(fa) click to toggle source

Generates the finite automata for the union of two different finite automatas.

@param fa [FiniteAutomata] the finite automata to union this one with

# File lib/fae/finite_automata.rb, line 86
def union(fa)
  perform_set_operation(:union, fa)
end

Private Instance Methods

evaluate_string(string) click to toggle source
# File lib/fae/finite_automata.rb, line 198
def evaluate_string(string)
  valid = true
  output = "\n#{string.colorize(:blue)}: "
  if (@language.string_is_valid(string))
    result = @states.first.evaluate(string, self)
    output << result[:output]
    if (result[:accepting] != string.expected)
      output << "\u2717".encode("utf-8").colorize(:red)
      valid = false
    else
      output << "\u2713".encode("utf-8").colorize(:green)
    end
  else
    output << "not valid for language #{@characters}".colorize(:red)
  end
  return { :valid => valid, :output => output }
end
perform_set_operation(type, fa) click to toggle source
# File lib/fae/finite_automata.rb, line 166
def perform_set_operation(type, fa)
  if @language.characters.uniq.sort != fa.language.characters.uniq.sort
    raise LanguageMismatchException, "Performing the #{type.to_s} requires the languages to be the same.".colorize(:red)
  end

  states  = []
  strings = []
  description = "the #{type.to_s} of #{@description} and #{fa.description}"
  new_fa = FiniteAutomata.new(@language, description)

  @states.each do |state|
    fa.states.each do |fa_state|
      name = state.name + fa_state.name
      accepting = false
      paths = {}
      state.paths.keys.each do |key|
        path = state.paths[key] + fa_state.paths[key]
        paths[key] = path
      end
      if ((type == :intersection && (state.accepting && fa_state.accepting)) || 
          (type == :difference && (state.accepting && !fa_state.accepting )) ||
          (type == :union && (state.accepting || fa_state.accepting)))
        accepting = true
      end
      states << State.new(name, paths, accepting)
    end
  end

  new_fa.add_states(states)
  new_fa
end