class Nfa2Dfa::Automaton

Representation of Automaton

Attributes

alphabet[RW]
stack[RW]
starting_state[RW]
states[RW]
transitions[RW]

Public Class Methods

init(path) click to toggle source
# File lib/automaton.rb, line 35
def self.init(path)
  File.file?(path) ? nil : (return nil)
  data_arr = []
  index = 0
  File.open(path).each_line do |line|
    data_arr[index] = line
    index = index + 1
  end
  validate(data_arr) ? get_valid_input(data_arr) : (return nil)
end
new(stat_arr, alph_arr, trans_arr, start) click to toggle source
# File lib/automaton.rb, line 225
def initialize(stat_arr, alph_arr, trans_arr, start)
  @states = stat_arr
  @alphabet = alph_arr
  @transitions = trans_arr
  @starting_state = start
end
validate(data_arr) click to toggle source
# File lib/automaton.rb, line 46
def self.validate(data_arr)
  parsed = []
  data_arr.each do |item|
    parsed.push item.split(' ')
  end
  validate_transitions(parsed[0], parsed[1], parsed[2]) &&
    validate_states(parsed[0], parsed[3], parsed[4])
end

Protected Class Methods

get_valid_input(data_arr) click to toggle source
# File lib/automaton.rb, line 96
def self.get_valid_input(data_arr)
  states = []
  data_arr[0].split(' ').each { |wrd| states.push State.new(wrd) }
  fin = data_arr[4].split(' ')
  states.each { |st| fin.include?(st.id) ? st.finalize : NIL }
  alphabet = []
  data_arr[1].split(' ').each { |wrd| alphabet.insert(alphabet.size, wrd) }
  transitions = []
  data_arr[2].split(' ').each do |wrd|
    trans = wrd.split('-')
    state1 = NIL
    state2 = NIL
    states.each do |item|
      trans[0] == item.id ? state1 = item : NIL
      trans[2] == item.id ? state2 = item : NIL
      state1 != NIL && state2 != NIL ? break : NIL
    end
    transitions.insert(transitions.size, Transition.new(
        state1, trans[1], state2))
    state1.add_transition(transitions[transitions.size - 1])
  end
  starting = NIL
  states.each do |item2|
    if item2.id == data_arr[3].split(' ')[0]
      starting = item2
      item2.to_starting_node
      break
    end
  end
  Automaton.new(states, alphabet, transitions, starting)
end

Private Class Methods

validate_states(states, start, final) click to toggle source

states must contain start and final states

# File lib/automaton.rb, line 233
def self.validate_states(states, start, final)
  if states.include? start[0]
    final.each do |fin|
      states.include?(fin) ? nil : (return false)
    end
    return true
  end
  false
end
validate_transitions(states, alphabet, transitions) click to toggle source
# File lib/automaton.rb, line 243
def self.validate_transitions(states, alphabet, transitions)
  transitions.each do |tr|
    trans = tr.split('-')
    if !((states.include? trans[0]) && (states.include? trans[2]) &&
          (alphabet.include? trans[1]))
      return false
    else
      # rubocop hates it :/
    end
  end
  true
end

Public Instance Methods

accepts?(data) click to toggle source
# File lib/automaton.rb, line 55
def accepts?(data)
  formatted_input = data.split(' ')
  @stack = []
  @stack.push(@starting_state)
  if formatted_input.size == 0
    @starting_state.is_final
  else
    recurs_accepts?(formatted_input, 0)
  end
end
determine() click to toggle source
# File lib/automaton.rb, line 75
def determine
  deterministic? ? self : determine_prot
end
deterministic?() click to toggle source
# File lib/automaton.rb, line 66
def deterministic?
  @states.each do |state|
    @alphabet.each do |char|
      state.get_next(char).size > 1 ? (return false) : nil
    end
  end
  true
end
to_graph(path) click to toggle source
# File lib/automaton.rb, line 24
def to_graph(path)
  g = GraphViz.new(:G, :type => :digraph)
  @states.each do |state|
    state.to_graph_node(g)
  end
  @transitions.each do |trans|
    trans.to_graph_transition(g)
  end
  g.output(:png => path)
end
to_str() click to toggle source
# File lib/automaton.rb, line 11
def to_str
  ret_val = ''
  str = ''
  ret_val += item_to_str(@states) + "\n" + item_to_str(@alphabet) +
    "\n" + item_to_str(@transitions) + "\n"
  ret_val += @starting_state.id + "\n"
  @states.each do |state|
    state.is_final ? str += state.id + ' ' : nil
  end
  ret_val += str.byteslice(0, str.length - 1)
  ret_val
end

Protected Instance Methods

determine_prot() click to toggle source

main determinization function

# File lib/automaton.rb, line 129
def determine_prot
  undetermined_states = []
  determined_states = []
  transits = []
  tot_transits = []
  curr_states = []
  undetermined_states[0] = @starting_state.clone
  new_begin_state = undetermined_states[0]
  while undetermined_states.size > 0
    temp_state = undetermined_states[0]
    curr_states.clear
    transits.clear
    @alphabet.each do |char|
      t_states_by_char = temp_state.get_next(char)
      if t_states_by_char.size > 0
        state_id = merge_state_names(t_states_by_char)
        state = find_state(
          state_id, determined_states, undetermined_states)
        if state
          transits.push(Transition.new(temp_state, char, state))
          tot_transits.push(Transition.new(temp_state, char, state))
        else
          state = State.new(state_id)
          state.associate_transitions(@transitions)
          undetermined_states.push(state)
          transits.push(Transition.new(temp_state, char, state))
          tot_transits.push(Transition.new(temp_state, char, state))
        end
      end
    end
    temp_state.clear_transitions
    transits.each do |transit|
      temp_state.add_transition(transit)
    end
    undetermined_states.delete(temp_state)
    determined_states.push(temp_state)
  end
  associate_finals(determined_states)
  Automaton.new(
    determined_states, @alphabet.clone, tot_transits, new_begin_state)
end
recurs_accepts?(data, index) click to toggle source
# File lib/automaton.rb, line 83
def recurs_accepts?(data, index)
  ret_val = false
  @stack.size == 0 ? (return false) : nil
  cnt = resolve_state_on_stack(data[index])
  index += 1
  if index == data.size
    cnt.times { @stack.pop.is_final ? ret_val = true : nil }
  else
    return recurs_accepts?(data, index)
  end
  ret_val
end

Private Instance Methods

associate_finals(stat) click to toggle source

Associates finals for determined automaton from states of nondetermined automaton

# File lib/automaton.rb, line 175
def associate_finals(stat)
  ret_val = []
  @states.each do |orig|
    if orig.is_final
      stat.each do |state|
        state.id.split(',').each do |id|
          if id == orig.id
            state.finalize
            ret_val.push(state)
            break 2
          end
        end
      end
    end
  end
  ret_val
end
find_state(state_id, container, container2) click to toggle source
# File lib/automaton.rb, line 193
def find_state(state_id, container, container2)
  str = ''
  state_id.split(' ').sort.each { |st| str += st }
  container.each do |state|
    state.id == state_id ? (return state) : nil
  end
  container2.each do |state|
    state.id == state_id ? (return state) : nil
  end
  NIL
end
item_to_str(array) click to toggle source
# File lib/automaton.rb, line 256
def item_to_str(array)
  str = ''
  array.each do |item|
    str += item.to_s + ' '
  end
  str.byteslice(0, str.length - 1)
end
merge_state_names(states) click to toggle source
# File lib/automaton.rb, line 205
def merge_state_names(states)
  arr = []
  states.each { |state| arr.push(state.id) }
  arr = arr.uniq.sort
  str = ''
  arr.each do |id|
    str += id + ','
  end
  str.byteslice(0, str.length - 1)
end
resolve_state_on_stack(char) click to toggle source
# File lib/automaton.rb, line 216
def resolve_state_on_stack(char)
  popped = @stack.pop
  arr = popped.get_next(char)
  arr.each do |item|
    @stack.push(item)
  end
  arr.size
end