class 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 60
def self.init(path)
  #nacteni ze souboru
  if File.file?(path)
    data_arr = Array.new
    index = 0
    File.open(path).each_line do |line|
      data_arr[index] = line
      index = index + 1
    end
    if validate(data_arr)
      get_valid_input(data_arr)
    else
      puts "Invalid input"
      NIL
    end
  else
    puts "Invalid input"
    NIL
  end
end
new(stat_arr, alph_arr, trans_arr, start) click to toggle source
# File lib/automaton.rb, line 283
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 81
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 134
def self.get_valid_input(data_arr)
  states = Array.new
  fin = data_arr[4].split(' ')
    
  data_arr[0].split(' ').each do |wrd|
    states.push State.new(wrd)
  end
  fin.include?(states[0].id)
  states.each do |st|
    (fin.include? st.id) ? st.finalize : NIL
  end
  alphabet = Array.new
  data_arr[1].split(' ').each do |wrd|
    alphabet.insert(alphabet.size, wrd)
  end
  transitions = Array.new
  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
# File lib/automaton.rb, line 290
def self.validate_states(states, start, final)
  if states.include? start[0]
    final.each do |fin|
      if !(states.include? fin)
        return false
      end
      return true
    end
    return false
  end
  return false
end
validate_transitions(states, alphabet, transitions) click to toggle source
# File lib/automaton.rb, line 303
def self.validate_transitions(states, alphabet, transitions)
  transitions.each do |tr|
    trans = tr.split('-')
    ((states.include? trans[0]) && (states.include? trans[2]) && (alphabet.include? trans[1])) ? NIL : (return false)
  end
  true
end

Public Instance Methods

accepts?(data) click to toggle source

format: pismeno<mezera>pismeno…

# File lib/automaton.rb, line 90
def accepts?(data)
  formatted_input = data.split(' ')
  @stack = Array.new
  @stack.push(@starting_state)
  formatted_input.size == 0 ? @starting_state.is_final : recurs_accepts?(formatted_input, 0)
end
determine() click to toggle source
# File lib/automaton.rb, line 108
def determine
  deterministic? ? self : determine_prot
end
deterministic?() click to toggle source
# File lib/automaton.rb, line 97
def deterministic?
  @states.each do |state|
    @alphabet.each do |char|
      if state.get_next(char).size > 1
        return false
      end
    end
  end
  true
end
to_graph(path) click to toggle source
# File lib/automaton.rb, line 42
def to_graph(path)
  g = GraphViz.new( :G, :type => :digraph)
  @states.each do |state|
    #puts state.id
    state.to_graph_node(g)
  end
  g.each_node() do |name, node|
    # puts name
  end
  @transitions.each do |trans|
    trans.to_graph_transition(g)
  end
  g.each_edge do |ed|
    #puts ed.node_one + " " + ed.node_two
  end
  g.output( :png => path )
end
to_str() click to toggle source
# File lib/automaton.rb, line 14
def to_str
  ret_val = ""
  str = ""
  @states.each do |state|
    str += state.id + " "
  end
  ret_val += str.byteslice(0, str.length-1) + "\n"
  str = ""
 @alphabet.each do |a|
    str+= a + " "
  end
  ret_val += str.byteslice(0, str.length-1) + "\n"
  str = ""
  @transitions.each do |trans|
    str += trans.beginning_state.id + "-" + trans.alphabet + "-" + trans.ending_state.id + " "
  end
  ret_val += str.byteslice(0, str.length-1) + "\n"
  str = ""
  ret_val += @starting_state.id + "\n"
  @states.each do |state|
    if state.is_final == true
      str += state.id + " "
    end
  end
  ret_val += str.byteslice(0, str.length-1)
  ret_val
end

Protected Instance Methods

determine_prot() click to toggle source
# File lib/automaton.rb, line 173
def determine_prot
  #https://edux.fit.cvut.cz/courses/BI-AAG/_media/lectures/03/bi-aag-03-operace_s_automaty-4.pdf
  undetermined_states = Array.new
  determined_states = Array.new
  transits = Array.new
  tot_transits = Array.new
  curr_states = Array.new
  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
          #Tvorba noveho statu
          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
  
  determined_states
  @alphabet
  tot_transits
  new_begin_state
  finals = 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 116
def recurs_accepts?(data, index)
  ret_val = false
  if @stack.size != 0
    cnt = resolve_state_on_stack(data[index])
    index = index + 1
    if index == data.size
      cnt.times do
        if @stack.pop.is_final
          ret_val = true
        end
      end
    else
      return recurs_accepts?(data,index)
    end
  end
  ret_val
end

Private Instance Methods

associate_finals(stat) click to toggle source
# File lib/automaton.rb, line 222
def associate_finals(stat)
  ret_val = Array.new
  @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 240
def find_state(state_id, container, container2)
  str = ""
  state_id.split(' ').sort.each do |st|
    str += st
  end
  # state_id = str.slice(0, str.size - 2)
  container.each do |state|
    if state.id == state_id
      return state
    end
  end
  container2.each do |state|
    if state.id == state_id
      return state
    end
  end
  NIL
end
merge_state_names(states) click to toggle source
# File lib/automaton.rb, line 259
def merge_state_names(states)
  arr = Array.new
  states.each do |state|
    arr.push(state.id)
  end
  arr = arr.uniq.sort
  last = arr.pop
  str = ""
  arr.each do |id|
    str += id + ","
  end
  str += last
  str
end
resolve_state_on_stack(char) click to toggle source
# File lib/automaton.rb, line 274
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