turing-m.cpp

这是个很好的源代码,有用的

// ==============================================================
//
//  Copyright (c) 2002-2003 by Alex Vinokur.
//
//  For conditions of distribution and use, see
//  copyright notice in version.h
//
// ==============================================================


// ##############################################################
//
//  SOFTWARE : Turing Machine (C++ Implementation)
//  FILE     : turing-m.cpp
//
//  DESCRIPTION :
//         Class TuringMachine (Implementation)
//
// ##############################################################


// ###############
#include "turing-m.h"


#define	SETW_RULE_NUMBER	4
#define	UNBELIEVABLE_NUMBER_OF_TAPES	100


// =========
size_t	TuringMachine::counter_s = 0;
		      

// =========
// =========
// Constructor-0
TuringMachine::TuringMachine (
	size_t	number_of_tapes_i,
	// ---
	const vector<vector<string> >& descr_i, 
	const vector<state_t>& initial_states_i, 
	const vector<state_t>& halting_states_i, 
	const vector<state_t>& internal_states_i,
	// ---
	const vector<symbol_t>& empty_symbols_alphabet_i, 
	const vector<symbol_t>& internal_alphabet_i,
	const vector<symbol_t>& input_alphabet_i,
	// ---
	const Transitions_t& transitions_i,
	// ---
	const string& msg_i
	)
	:
	descr_ (descr_i),
	initial_states_ (initial_states_i),
	halting_states_ (halting_states_i),
	internal_states_ (internal_states_i),
	transitions_ (transitions_i),
	check_results_ (true),
	cur_input_set_no_ (0),
	transition_statistics_ (transitions_i.size()),
	max_state_size_ (0),
	max_symbol_size_ (0),
	serial_no_ (++counter_s)
{

  IF_NOT_EMPTY (msg_i, 5, '=');

typedef Tapes_t::value_type value_type;
pair<Tapes_t::iterator, bool> the_pair;

  if (number_of_tapes_i == 0)
  {
    check_results_ = false;
    FATAL_MSG	("Illegal number of tapes : "
		<< number_of_tapes_i
		);
    return;
  }

  if (number_of_tapes_i > UNBELIEVABLE_NUMBER_OF_TAPES)
  {
    WARNING_MSG	("Unbelievable number of tapes : "
		<< number_of_tapes_i
		);
  }

  for (size_t i = 0; i < number_of_tapes_i; i++)
  {
    the_pair = tapes_.insert (value_type(i, Tape (empty_symbols_alphabet_i, internal_alphabet_i, input_alphabet_i)));
    if (!the_pair.second)
    {
      check_results_ = false;
      FATAL_MSG	("The same current position occurs more tjan once in transition rules");
      break;
    }
    assert (the_pair.second);

    if (!the_pair.first->second.check_results_)
    {
      check_results_ = false;
      FATAL_MSG	("Tape#" << i << " has problems");
      break;
    }
  }


  // ------------------------------------
  set_max_state_size();
  set_max_symbol_size();


  // ---------------
  show_env();

  // ----------------------
  if (check_results_)	check_results_ = check_states ();
  if (check_results_)	check_results_ = check_alphabets ();
  if (check_results_)	check_results_ = check_transition ();

} 

// =========
// Destructor
TuringMachine::~TuringMachine ()
{
} 

// =========
void TuringMachine::set_max_state_size()
{
vector<state_t>	tmp_all_states = get_all_states();
  assert (max_state_size_ == 0);
  for (size_t i = 0; i < tmp_all_states.size(); i++)
  {
    max_state_size_ = MAX_VALUE (max_state_size_, tmp_all_states[i].size()); 
  }

}

// =========
void TuringMachine::set_max_symbol_size()
{
Tapes_t::const_iterator iter;
  assert (max_symbol_size_ == 0);
  for (iter = tapes_.begin(); iter != tapes_.end(); iter++)
  {
    max_symbol_size_ = MAX_VALUE (max_symbol_size_, iter->second.max_symbol_size_);
  }
}

// =========
vector<state_t> TuringMachine::get_all_states () const
{
vector<state_t>	ret_vector;

  copy (initial_states_.begin(), initial_states_.end(), back_inserter(ret_vector));
  copy (halting_states_.begin(), halting_states_.end(), back_inserter(ret_vector));
  copy (internal_states_.begin(), internal_states_.end(), back_inserter(ret_vector));

  return ret_vector;

}


// =========
void TuringMachine::set_input (const vector<vector<symbol_t> >& input_words_i)
{
  assert (cur_states_.empty());
  cur_states_.push_back (initial_states_.front());
  for (size_t i = 0; i < tapes_.size(); i++) tapes_[i].tape_.clear();

  for (size_t i = 0; i < input_words_i.size(); i++) 
  {
    for (size_t j = 0; j < input_words_i[i].size(); j++) 
    {
      tapes_[i].tape_.push_back (input_words_i[i][j]);
    }
  }
}


// =========
void TuringMachine::clear_it ()
{
  cur_states_.clear();
  cur_transitions_.clear();
  cur_input_set_no_++;

  for (size_t i = 0; i < transition_statistics_.size(); i++)
  {
    transition_statistics_[i] = 0;
  } 


Tapes_t::iterator iter;
  for (iter = tapes_.begin(); iter != tapes_.end(); iter++)
  {
    iter->second.clear_it();
  }

}


// =========
bool	TuringMachine::check_input_words (const vector<vector<symbol_t> >& input_words_i) const
{
Tapes_t::const_iterator	iter;

  if (input_words_i.empty())
  {
    FATAL_MSG	("No input words");
    return false;
  }

  if (input_words_i.size() != tapes_.size())
  {
    FATAL_MSG	("Number of input words ("
		<< input_words_i.size()
		<< ") is NOT equal number of tapes ("
		<< tapes_.size()
		<< ")"
		);
    return false;  
  }

size_t i;
  for (i = 0, iter = tapes_.begin(); i < input_words_i.size(); i++, iter++)
  {
    assert (iter->first == i);
    if (input_words_i[i].empty())
    {
      FATAL_MSG	("No input word for tape#"
		<< i
		);
      return false;
    }

    for (size_t j = 0; j < input_words_i[i].size(); j++)
    {
      if (!(iter->second.is_input_symbol (input_words_i[i][j])))
      {
        if (!((j == 0) && (input_words_i[i].size() == 1) && (iter->second.is_empty_symbol (input_words_i[i][j]))))
        { 
          FATAL_MSG	("Tape#"
			<< i
			<< ", symbol#"
			<< j
			<< " : "
			<< "\""
			<< input_words_i[i][j]
			<< "\""
			<< " is NOT an input symbol"
			);
          return false;
        }
      }
    } // for (size_t j = 0; ...
  } // for (size_t i = 0; ...

  return true;
}


// =========
void TuringMachine::show_input (
	const vector<vector<symbol_t> >& input_words_i,
	bool fool_flag_i
	) const
{
  cout << endl;
  cout << "\t"
       << string (5, '#')
       << " ";
  if (fool_flag_i)
  {
    cout << ""
         << getstr_id_info ();
  }
  cout << "Input words on tape(s)"
       << " " 
       << string (5, '#')
       << endl;
  for (size_t i = 0; i < input_words_i.size(); i++)
  {
    cout << "Tape#" << i << " : ";
    for (size_t j = 0; j < input_words_i[i].size(); j++)
    {
      cout << setw (max_symbol_size_) << to_string (input_words_i[i][j]).c_str() << " ";
    }
    //copy (input_words_i[i].begin(), input_words_i[i].end(), ostream_iterator<symbol_t> (cout, " "));
    cout << endl;
  }
  cout << endl;
}

// =========
bool TuringMachine::perform_step (state_t& state_o, vector<symbol_t>& scanned_symbols_o, const string& msg_i)
{
  IF_NOT_EMPTY (msg_i, 5, '=');

vector<symbol_t>	scanned_symbols;
  for (size_t i = 0; i < tapes_.size(); i++)
  {
    scanned_symbols.push_back(tapes_[i].get_position_symbol ());
  }
  scanned_symbols_o.clear(); 
  copy (scanned_symbols.begin(), scanned_symbols.end(), back_inserter(scanned_symbols_o));

const Transitions_t::const_iterator iter = transitions_.find (CurSituation(*cur_states_.rbegin(), scanned_symbols));

  if (iter == transitions_.end())	return false;

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

  cur_transitions_.push_back (iter);
  cur_states_.push_back (iter->second.get_state ());
  for (size_t i = 0; i < tapes_.size(); i++)
  {
    tapes_[i].set_position_symbol (iter->second.get_symbol (i));
    tapes_[i].shift_position (iter->second.get_shift(i));
  }
 
  state_o = *cur_states_.rbegin();;
  return true;

}

// =========
bool TuringMachine::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 Turing Machine definition");
    return false;
  }

  cout << endl;
  if (!check_input_words(input_words_i))
  {
    show_input (input_words_i, false);
    FATAL_MSG	("Invalid input words");
    cur_input_set_no_++;
    return false;
  }
  clear_it ();
  show_input (input_words_i);
  set_input (input_words_i);


  // ------------------
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;

  show_situation (getstr_id_info () + "Initial Configuration");
  for (int i = 0; ; i++)
  {
    ret_bool_value = perform_step (state, scanned_symbols);  
    if (!ret_bool_value)
    { 
      cout << "\t" << "Failure : 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 is not halting one" << endl;
      break;
    }
    show_situation (getstr_id_info () + "Configuration#" + to_string (i + 1));
    if (is_halting_state (state))
    {
      cout << "\t" << "Success : Current state is halting one" << endl;
      break;
    }
  } // for (i = 

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;

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

  return ret_bool_value;
}


// =========
void TuringMachine::show_env () const
{
  cout << endl;
  cout << "\t###### Turing Machine Definition ######" << endl;

  cout << endl;
  show_descr ();

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

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

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

}


// =========
void TuringMachine::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 TuringMachine::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() << " ";
  }