turing-m.cpp

The program simulates a Nondeterministic Multitape Turing Machine. It works as ordinary (Determinist

// =========
Transitions_t::const_iterator NondeterministicTuringMachine::get_processed_transition() const
{
  assert (!cur_status_.empty());

size_t id;
const bool rc = get_next_id_to_be_processed (id);
  assert (rc);
  assert (id < cur_status_.size());

  return cur_status_[id].the_transition_;
}



// =========
int& NondeterministicTuringMachine::get_cur_transition_subno()
{
  assert (!cur_status_.empty());
  return cur_status_.back().the_transition_subno_;
}



// =========
int NondeterministicTuringMachine::get_processed_transition_subno() const
{
  assert (!cur_status_.empty());

size_t id;
const bool rc = get_next_id_to_be_processed (id);
  assert (rc);
  assert (id < cur_status_.size());

  return cur_status_[id].the_transition_subno_;
}



// =========
vector<int> NondeterministicTuringMachine::get_cur_branch() const
{
  assert (!cur_status_.empty());
  return cur_status_.back().the_branch_;
}



// =========
vector<int> NondeterministicTuringMachine::get_processed_branch() const
{
  assert (!cur_status_.empty());

size_t id;
const bool rc = get_next_id_to_be_processed (id);
  assert (rc);
  assert (id < cur_status_.size());

  return cur_status_[id].the_branch_;
}



// =========
string NondeterministicTuringMachine::getstr_cur_branch() const
{
  assert (!cur_status_.empty());
vector<int> branch (get_cur_branch());
ostringstream oss;
  copy (branch.begin(), branch.end(), ostream_iterator<int> (oss, "-"));

const string str (oss.str());
  return str.substr (0, str.size() - 1); 
}



// =========
string NondeterministicTuringMachine::getstr_processed_branch() const
{
  assert (!cur_status_.empty());
vector<int> branch (get_processed_branch());
ostringstream oss;
  copy (branch.begin(), branch.end(), ostream_iterator<int> (oss, "-"));

const string str (oss.str());
  return str.substr (0, str.size() - 1); 
}




// =========
bool NondeterministicTuringMachine::get_next_id_to_be_processed (size_t& id_o) const
{
  assert (!cur_status_.empty());
  id_o = MachineStatus::next_id_to_be_processed_s;
  return (MachineStatus::next_id_to_be_processed_s < cur_status_.size());
}


// =========
// =========
bool NondeterministicTuringMachine::perform_step (
		const state_t& state_i, 
		const vector<symbol_t>& scanned_symbols_i, 
		Transitions_t::const_iterator& find_iter_o,
		const string& msg_i
		)
{
  IF_NOT_EMPTY (msg_i, 5, '=');

  assert (state_i != symbol_t());

find_iter_o = transitions_.find (CurSituation(state_i, scanned_symbols_i));

  if (find_iter_o == transitions_.end())	
  {
    assert (state_i != symbol_t());
    return false;
  }

size_t dist = distance (transitions_.begin(), find_iter_o);
  assert (dist < transitions_.size());
  transition_statistics_[dist]++;

  // -----------------------
  // -----------------------
const Tapes_t last_tapes (get_processed_tapes());
const vector<int> last_branch (get_processed_branch());

const size_t next_configuration_no = get_cur_configuration () + 1;

  for (size_t id = 0; id < find_iter_o->second.size(); id++)
  {
    const int subno = id + 1;
    cur_status_.push_back (MachineStatus());

    cur_status_.back().the_branch_ = last_branch;
    cur_status_.back().the_branch_.push_back(subno);
    time_used_ = MAX_VALUE (time_used_, cur_status_.back().the_branch_.size());

    get_cur_configuration() = next_configuration_no;

    Tapes_t::iterator pos_iter;
    for (pos_iter = get_cur_tapes().begin(); pos_iter != get_cur_tapes().end(); pos_iter++)
    {
      pos_iter->second.clear_it();
    }
    get_cur_tapes().clear();

    get_cur_tapes() = last_tapes;
    // -----------------------

    get_cur_transition() = find_iter_o;
    get_cur_transition_subno() = subno;
    get_cur_state() = find_iter_o->second[id].get_state ();
    for (size_t i = 0; i < get_cur_tapes().size(); i++)
    {
      get_cur_tapes()[i].set_symbol (find_iter_o->second[id].get_symbol (i));
      get_cur_tapes()[i].shift_position (find_iter_o->second[id].get_shift(i));
    }
 
    assert (get_cur_state() != symbol_t());
  }

  MachineStatus::next_id_to_be_processed_s++;

  return true;

}

// =========
bool NondeterministicTuringMachine::process_input (
		const vector<vector<symbol_t> >& input_words_i,
		const string& msg_i
		)
{
  IF_NOT_EMPTY (msg_i, 5, '=');

  if (!check_results_)
  {
    FATAL_MSG	("Invalid Nondeterministic Turing Machine definition");
    return false;
  }

vector<vector<symbol_t> > input_words (input_words_i);
vector<long> init_pos;

  cout << endl;
  if (!check_input_words(input_words, init_pos))
  {
    show_input (input_words, init_pos, false);
    FATAL_MSG	("Invalid input words");
    cur_input_set_no_++;
    return false;
  }
  clear_it ();
  assert (input_words.size() == init_pos.size());
  show_input (input_words, init_pos);
  set_input (input_words, init_pos);


  // ------------------
state_t	 state;
vector<symbol_t>	scanned_symbols;

bool	ret_bool_value;

  cout << endl;
  cout << endl;
  cout << "\t"
       << string (5, '#') 
       << " "
       << getstr_id_info ()
       << "Processing"
       << " "
       << string (5, '#') 
       << endl;

Transitions_t::const_iterator find_iter = transitions_.end();

size_t next_id;

  for (int step_no = 0; ; step_no++)
  {

    const int actual_step_no = step_no;
    if (!get_next_id_to_be_processed (next_id)) break;
    assert (next_id < cur_status_.size());

    scanned_symbols.clear();
    for (size_t i = 0; i < cur_status_[next_id].the_tapes_.size(); i++)
    {
      scanned_symbols.push_back(cur_status_[next_id].the_tapes_[i].get_scanned_symbol ());
    }

    // -------------------------------------
    show2_situation (getstr_id_info (), actual_step_no);
    ret_bool_value = perform_step (cur_status_[next_id].the_state_, scanned_symbols, find_iter);  

    state = get_processed_state();

    // -------------------
    show1_situation (find_iter);
    assert (((find_iter != transitions_.end()) && (ret_bool_value)) || ((find_iter == transitions_.end()) && (!ret_bool_value)));
    if (!ret_bool_value)
    { 
      cout << "\t" << getstr_id_info () << "Failure" << (is_actually_nondeterministic_ ? " of the Branch" : "") << endl;
      cout << "\t" << "  1) There exists no appropriate rule for" << endl;
      cout << "\t" << "     " << state << " [ ";
      copy (scanned_symbols.begin(), scanned_symbols.end(), ostream_iterator<string> (cout, " "));
      cout << "]" << endl;
      cout << "\t" << "  2) Current state (" << state << ") is not halting one" << endl;

      cout << endl;
      cout << endl;

      MachineStatus::next_id_to_be_processed_s++;
      continue;
    }

    assert (ret_bool_value);
    // -------------------
    // show2_situation (getstr_id_info (), "Configuration#" + to_string (actual_step_no));

    // -------------------
    if (is_halting_state (state))
    {
      show2_situation (getstr_id_info (), actual_step_no + 1);

      cout << "\t" << getstr_id_info () << "Success : Current state (" << state << ") is halting one" << endl;
      cout << endl;
      cout << endl;

      MachineStatus::next_id_to_be_processed_s++;
      break;
    }

  } // for (step_no = 

const size_t the2_setw = 3;

ostringstream oss;
  oss << "" 
       << string (the2_setw, '-')
       << " "
       << getstr_id_info (true)
       << " Result : Input word(s) " 
       << (ret_bool_value ? "ACCEPTED" : "REJECTED") 
       << " " 
       << string (the2_setw, '-'); 
  
const size_t the1_setw = oss.str().size();

const string prefix (3, ' ');

  cout << endl;
  cout << prefix << string (the1_setw, '-') << endl;
  cout << prefix 
       << oss.str()
       << endl;
  cout << prefix << string (the1_setw, '-') << endl;
  cout <<  endl;

  // -----------------------------
  assert (output_size_ == 0);
  output_size_ = get_output_size();

  assert (space_used_ == 0);
  space_used_ = get_space_used();

  show_resources_report ();

  // -----------------------------
  show_statistics ();

  return ret_bool_value;
}


// =========
void NondeterministicTuringMachine::show_env () const
{
  cout << endl;
  cout << "\t###### Nondeterministic Turing Machine Definition ######" << endl;
  if (is_actually_nondeterministic_)
  {
    cout << "\t###### This Machine is actually Nondeterministic  ######" << endl;
  }
  else
  {
    cout << "\t###### This Machine is actually Deterministic!!!  ######" << endl;
  }

  cout << endl;
  show_descr ();

  cout << endl;
  cout << endl;
  show_states ();

  cout << endl;
  cout << endl;
  show_alphabets();

  cout << endl;
  cout << endl;
  show_transition ();

}


// =========
void NondeterministicTuringMachine::show_descr (const string& msg_i) const
{
  cout << "\t   ====== Description ======" << endl;

  IF_NOT_EMPTY (msg_i, 5, '=');

  if (descr_.empty())
  {
    cout << "No description" << endl;
  }

  for (size_t i = 0; i < descr_.size(); i++)
  {
    copy (descr_[i].begin(), descr_[i].end(), ostream_iterator<string> (cout, " "));
    cout << endl;
  }

}


// =========
void NondeterministicTuringMachine::show_states (const string& msg_i) const
{
  cout << "\t   ====== States Definition ======" << endl;

  IF_NOT_EMPTY (msg_i, 5, '=');


string text_initial_states ("Initial states");
string text_halting_states ("Halting states");
string text_internal_states ("Internal states");
size_t text_max_size = 0;

  text_max_size	= MAX_VALUE(text_max_size, text_initial_states.size());
  text_max_size	= MAX_VALUE(text_max_size, text_halting_states.size());
  text_max_size	= MAX_VALUE(text_max_size, text_internal_states.size());


  cout << setw(text_max_size) << left << text_initial_states.c_str() << " : ";
  for (size_t i = 0; i < initial_states_.size(); i++)
  {
    cout << setw (max_state_size_) << initial_states_[i].c_str() << " ";
  }
  cout << endl;

  cout << setw(text_max_size) << left << text_halting_states.c_str() << " : ";
  for (size_t i = 0; i < halting_states_.size(); i++)
  {
    cout << setw (max_state_size_) << halting_states_[i].c_str() << " ";
  }
  cout << endl;

  cout << setw(text_max_size) << left << text_internal_states.c_str() << " : ";
  for (size_t i = 0; i < internal_states_.size(); i++)
  {
    cout << setw (max_state_size_) << internal_states_[i].c_str() << " ";
  }
  cout << endl;


}

// =========
void NondeterministicTuringMachine::show_alphabet (const Tapes_t::const_iterator& iter_i) const
{
  iter_i->second.show_alphabet();
}

// =========
void NondeterministicTuringMachine::show_alphabets () const
{
Tapes_t::const_iterator pos_iter;
  cout << "\t   ====== Alphabet Definition ======" << endl;
  for (pos_iter = init_tapes_.begin(); pos_iter != init_tapes_.end(); pos_iter++)
  {
    cout << "\t      ------ Tape# " << distance (init_tapes_.begin(), pos_iter) << " ------" << endl;
    show_alphabet (pos_iter);
    cout << endl;
  }
}

// =========
void NondeterministicTuringMachine::show_transition () const
{
Transitions_t::const_iterator pos_iter;
  cout << "\t   ====== Transition Rules Definition ======" << endl;
  for (pos_iter = transitions_.begin(); pos_iter != transitions_.end(); pos_iter++)
  {
    cout << getstr_rule_S (
		is_actually_nondeterministic_, 
		transitions_.begin(), 
		pos_iter, 
		max_state_size_, 
		max_symbol_size_
		);
  }
  cout << endl;
}

// =========
string NondeterministicTuringMachine::getstr_rule_S (
		bool is_actually_nondeterministic_i,
		Transitions_t::const_iterator iter1_i,
		Transitions_t::const_iterator iter2_i,
		size_t	max_state_size_i,
		size_t	max_symbol_size_i,
		int	subno_i
		)
{
  assert (subno_i != 0);
  assert ((subno_i > 0) || (subno_i == -1));

ostringstream oss;
  for (size_t k = 0; k < iter2_i->second.size(); k++)
  {
    if ((subno_i == -1)	|| (size_t(subno_i) == (k + 1)))
    {
      oss << ""
          << "Rule#"
          << setw (SETW_RULE_NUMBER)
          << right
          << distance (iter1_i, iter2_i);
      if (is_actually_nondeterministic_i)
      {
        oss << "-"
            << (k + 1);
      }
      oss << " :   "
          << setw (max_state_size_i)
          << iter2_i->first.get_state().c_str()
          << " [ " 
          << iter2_i->first.getstr_symbols(max_symbol_size_i)
          << "] ---> "
          << setw (max_state_size_i)
          << iter2_i->second[k].get_state().c_str()
          << " [ " 
          << iter2_i->second[k].getstr_symbols_and_shifts(max_symbol_size_i)
          << "]"
          << endl;
    }
  }

  return oss.str();
}
   
// =========
void NondeterministicTuringMachine::show_tape (const Tapes_t::const_iterator& iter_i) const
{
  iter_i->second.show_tape();
}


// =========
void NondeterministicTuringMachine::show1_situation (
	const Transitions_t::const_iterator& find_iter_i,
	bool init_configuration_i
	) const
{
  assert (!cur_status_.empty());
  assert (!init_configuration_i);

  if (find_iter_i != transitions_.end())
  {
    for (size_t k = 0; k < find_iter_i->second.size(); k++)
    {
      cout << "\t" 
           << getstr_id_info ()
           << "Applied " 
           << getstr_rule_S (
		is_actually_nondeterministic_, 
		transitions_.begin(), 
		find_iter_i, 
		max_state_size_, 
		max_symbol_size_, 
		k + 1
		); 
    }
  }
  else
  {
      cout << "\t" 
           << getstr_id_info ()