run.cpp

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

  cout	<< space3
	<< string (setw10, '=')
	<< " "
	<< text1
	<< " "
	<< string (setw10, '=')
	<< endl;

  cout	<< space4 << "Row#1 : " << "list of empty symbols (empty symbols alphabet)" << endl;
  cout	<< space4 << "Row#2 : " << "list of internal symbols" << endl;
  cout	<< space4 << "Row#3 : " << "list of input symbols" << endl;


  cout	<< space3 << string (setw10 + 1 + text1.size() + 1 + setw10, '=') << endl;

} // show_alphabet_file_structure_S



// =========
void Run::show_descr_file_structure_S  ()
{
const string text1 ("Description file structure");

  cout	<< endl;
  cout	<< space3
	<< string (setw10, '=')
	<< " "
	<< text1
	<< " "
	<< string (setw10, '=')
	<< endl;

  cout	<< space4 << "--- Your text :" << endl;
  cout	<< space4 << "--- Description of your Nondeterministic Turing Machine" << endl;

  cout	<< space3 << string (setw10 + 1 + text1.size() + 1 + setw10, '=') << endl;

} // show_descr_file_structure_S



// =========
void Run::show_states_file_structure_S  ()
{
// ------------------------------------------
// States file structure :
// Row#1 : list of initial states
// Row#2 : list of halting states
// Row#3 : list of internal states
// ------------------------------------------
const string text1 ("States file structure");

  cout	<< endl;
  cout	<< space3
	<< string (setw10, '=')
	<< " "
	<< text1
	<< " "
	<< string (setw10, '=')
	<< endl;

  cout	<< space4 << "Row#1 : " << "list of initial states" << endl;
  cout	<< space4 << "Row#2 : " << "list of halting states" << endl;
  cout	<< space4 << "Row#3 : " << "list of internal states" << endl;


  cout	<< space3 << string (setw10 + 1 + text1.size() + 1 + setw10, '=') << endl;

} // show_states_file_structure_S


// =========
void Run::show_transitions_file_structure () const
{
  show_transitions_file_structure_S();

const string text1 ("Transition file structure");

  cout	<< endl;
  cout	<< space3
	<< string (setw10, '=')
	<< " "
	<< text1
	<< " "
	<< string (setw10, '=')
	<< endl;

size_t	field_no = 0;
const string text_field ("Field#");

const string text2 ("current symbol");
const string text3 ("next symbol");
const string text4 ("shift");
size_t the_setw = 0;

  the_setw = MAX_VALUE (the_setw, text2.size());
  the_setw = MAX_VALUE (the_setw, text3.size());
  the_setw = MAX_VALUE (the_setw, text4.size());
  assert (the_setw != 0);

  cout	<< space4 << "Each row contains some transition rule" << endl;
  cout	<< space4 << "Number of tapes = " << number_of_tapes_ << endl;

  cout	<< space3 << string (setw10 + 1 + text1.size() + 1 + setw10, '-') << endl;

  cout << space4 << text_field << setw(4) << right << field_no++ << " : " << "current state" << endl;
  for (size_t i = 0; i < number_of_tapes_; i++)
  {
    cout << space4 << text_field << setw(4) << right << field_no++ << " : " << setw (the_setw) << left << text2.c_str() << " on tape#" << i << endl;
  }

  cout	<< space4 << text_field << setw(4) << right << field_no++ << " : " << "next state" << endl;
  for (size_t i = 0; i < number_of_tapes_; i++)
  {
    cout << space4 << text_field << setw(4) << right << field_no++ << " : " << setw (the_setw) << left << text3.c_str() << " on tape#" << i << endl;
    cout << space4 << text_field << setw(4) << right << field_no++ << " : " << setw (the_setw) << left << text4.c_str() << " on tape#" << i << endl;
  }

  cout	<< space3 << string (setw10 + 1 + text1.size() + 1 + setw10, '=') << endl;

} // show_transitions_file_structure



// =========
void Run::show_transitions_file_structure_S()
{
const string text1 ("Transition file structure");

  cout	<< endl;
  cout	<< space3
	<< string (setw10, '=')
	<< " "
	<< text1
	<< " "
	<< string (setw10, '=')
	<< endl;

size_t	field_no = 0;
const string field_plus_no ("n+");

const string text_field ("Field#");

const string text2 ("current symbol");
const string text3 ("next symbol");
const string text4 ("shift");
size_t the_setw = 0;

  the_setw = MAX_VALUE (the_setw, text2.size());
  the_setw = MAX_VALUE (the_setw, text3.size());
  the_setw = MAX_VALUE (the_setw, text4.size());


size_t	tmp_no = 3;
const size_t	next_setw = field_plus_no.size() + 2;
const size_t	cur_setw = next_setw + 1;


  cout	<< space4 << "Each row contains some transition rule" << endl;
  cout	<< space4 << "Let n be number of tapes" << endl;

  cout	<< space3 << string (setw10 + 1 + text1.size() + 1 + setw10, '-') << endl;

  cout << space4 << text_field << setw(cur_setw) << right << field_no++ << " : " << "current state" << endl;
  for (size_t i = 0; i < tmp_no; i++)
  {
    cout << space4 << text_field << setw(cur_setw) << right << field_no++ << " : " << setw (the_setw) << left << text2.c_str() << " on tape#" << i << endl;
  }
  cout << space4 << string (20, '.') << endl;

  field_no = 1;
  cout	<< space4 << text_field << setw (next_setw) << right << setw (next_setw) << right << field_plus_no.c_str() << field_no++ << " : " << "next state" << endl;
  for (size_t i = 0; i < tmp_no; i++)
  {
    cout << space4 << text_field << setw (next_setw) << right << field_plus_no.c_str() << field_no++ << " : " << setw (the_setw) << left << text3.c_str() << " on tape#" << i << endl;
    cout << space4 << text_field << setw (next_setw) << right << field_plus_no.c_str() << field_no++ << " : " << setw (the_setw) << left << text4.c_str() << " on tape#" << i << endl;
  }
  cout << space4 << string (20, '.') << endl;

  cout	<< space3 << string (setw10 + 1 + text1.size() + 1 + setw10, '=') << endl;

} // show_transitions_file_structure_S


			     
// =========
void Run::show_input_words_file_structure_S ()
{
const string text1 ("Input words file structure");

  cout	<< endl;
  cout	<< space3
	<< string (setw10, '=')
	<< " "
	<< text1
	<< " "
	<< string (setw10, '=')
	<< endl;

size_t	row_no = 0;
const string last_row_no ("n-1");

const string text_row ("Row#");

size_t the_setw = 0;

const string text2 ("input word");
  the_setw = MAX_VALUE (the_setw, text2.size());
  assert (the_setw != 0);

size_t	tmp_no = 3;
const size_t	the2_setw = last_row_no.size() + 2;


  cout	<< space4 << "Each row contains input word for some tape" << endl;
  cout	<< space4 << "Let n be number of tapes" << endl;
  cout	<< space3 << string (setw10 + 1 + text1.size() + 1 + setw10, '-') << endl;

  for (size_t i = 0; i < tmp_no; i++)
  {
    cout << space4 << text_row << setw(the2_setw) << right << row_no++ << " : " << setw (the_setw) << left << text2.c_str() << " on tape#" << i << endl;
  }
  cout << space4 << string (20, '.') << endl;

  cout << space4 << text_row << setw(the2_setw) << right << last_row_no.c_str() << " : " << setw (the_setw) << left << text2.c_str() << " on tape#" << "(n-1)" << endl;

  cout	<< space3 << string (setw10 + 1 + text1.size() + 1 + setw10, '=') << endl;

  cout	<< space3
        << "Note! Symbol " 
        << "\"" 
        << HEAD_START_POSITION_POINTER_REDERVED_SYMBOL 
        << "\"" 
        << " may be used as (optional) pointer"
        << endl

        << space3
        << "      to start position of machine head on tape(s)."
        << endl

        << space3
        << "      In this case that symbol should be inserted"
        << endl

        << space3
        << "      before a pointed position"
        << endl;


} // show_input_words_file_structure_S


// =========
void Run::show_metafile_sample_S ()
{
const string text1("Metafile sample");
vector<vector<string> >	sample;

  sample.push_back(vector<string>());
  sample.rbegin()->push_back("sample1.dsc");
  sample.rbegin()->push_back("2");
  sample.rbegin()->push_back("sample1.sta");
  sample.rbegin()->push_back("sample1.abt");
  sample.rbegin()->push_back("sample1.rul");
  sample.rbegin()->push_back("sample11.in");
  sample.rbegin()->push_back("sample12.in");
  sample.rbegin()->push_back("sample13.in");

  sample.push_back(vector<string>());
  sample.rbegin()->push_back("sample2.dsc");
  sample.rbegin()->push_back("5");
  sample.rbegin()->push_back("sample2.sta");
  sample.rbegin()->push_back("sample2.abt");
  sample.rbegin()->push_back("sample2.rul");
  sample.rbegin()->push_back("sample21.in");


  sample.push_back(vector<string>());
  sample.rbegin()->push_back("descr.txt");
  sample.rbegin()->push_back("3");
  sample.rbegin()->push_back("states.txt");
  sample.rbegin()->push_back("alphabet.txt");
  sample.rbegin()->push_back("rules.txt");
  sample.rbegin()->push_back("input1.txt");
  sample.rbegin()->push_back("input2.txt");


  sample.push_back(vector<string>());
  sample.rbegin()->push_back("sample3.dsc");
  sample.rbegin()->push_back("1");
  sample.rbegin()->push_back("sample3.sta");
  sample.rbegin()->push_back("sample3.abt");
  sample.rbegin()->push_back("sample3.rul");
  sample.rbegin()->push_back("sample31.in");
  sample.rbegin()->push_back("sample32.in");



  cout	<< endl;
  cout	<< space3
	<< string (setw10, '#')
	<< " "
	<< text1
	<< " "
	<< string (setw10, '#')
	<< endl;

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

  cout	<< space3 << string (setw10 + 1 + text1.size() + 1 + setw10, '#') << endl;

}


// =========
void Run::show_descr_file_sample_S  ()
{
const string text1("Description file sample");
vector<vector<string> >	sample;


  sample.push_back(vector<string>());
  sample.rbegin()->push_back("A Noneterministic Turing Machine example : Partition Problem");

  sample.push_back(vector<string>());
  sample.rbegin()->push_back("* from \"The Design and Analysis of Computer Algorithms [1976]\"");

  sample.push_back(vector<string>());
  sample.rbegin()->push_back("* by A.V.Aho, J.E.Hopcroft, J.D.Ullman");

  sample.push_back(vector<string>());
  sample.rbegin()->push_back("* --> See examples 10.1");

  cout	<< endl;
  cout	<< space3
	<< string (setw10, '=')
	<< " "
	<< text1
	<< " "
	<< string (setw10, '=')
	<< endl;

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

  cout	<< space3 << string (setw10 + 1 + text1.size() + 1 + setw10, '=') << endl;

}

// =========
void Run::show_states_file_sample_S  ()
{
const string text1("States file sample");
vector<vector<string> >	sample;

  sample.push_back(vector<string>());
  sample.rbegin()->push_back("q0");

  sample.push_back(vector<string>());
  sample.rbegin()->push_back("q5");

  sample.push_back(vector<string>());
  sample.rbegin()->push_back("q1");
  sample.rbegin()->push_back("q2");
  sample.rbegin()->push_back("q3");
  sample.rbegin()->push_back("q4");

  cout	<< endl;
  cout	<< space3
	<< string (setw10, '=')
	<< " "
	<< text1
	<< " "
	<< string (setw10, '=')
	<< endl;

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

  cout	<< space3 << string (setw10 + 1 + text1.size() + 1 + setw10, '=') << endl;

}


// =========
void Run::show_alphabet_file_sample_S  ()
{
const string text1("Alphabet file sample");
vector<vector<string> >	sample;

  sample.push_back(vector<string>());
  sample.rbegin()->push_back("b");

  sample.push_back(vector<string>());
  sample.rbegin()->push_back("x");

  sample.push_back(vector<string>());
  sample.rbegin()->push_back("0");
  sample.rbegin()->push_back("1");

  cout	<< endl;
  cout	<< space3
	<< string (setw10, '=')
	<< " "
	<< text1
	<< " "
	<< string (setw10, '=')
	<< endl;

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

  cout	<< space3 << string (setw10 + 1 + text1.size() + 1 + setw10, '=') << endl;
}

// =========
void Run::show_transitions_file_sample_S  ()
{
const string text1("Transitions file sample");
const string text2("Number of tapes = 3");
vector<vector<string> >	sample;

typedef char trow_t [10];

const trow_t row01[] = {"q0", " 1", "b", "b", "    q1", " 1", "N", " x", "R", " x", "R"}; 
const trow_t row02[] = {"q1", " 1", "b", "b", "    q2", " 1", "R", " b", "N", " b", "N"}; 
const trow_t row03[] = {"q1", " 1", "b", "b", "    q3", " 1", "R", " b", "N", " b", "N"}; 
const trow_t row04[] = {"q2", " 0", "b", "b", "    q2", " 0", "R", " 0", "R", " b", "N"}; 
const trow_t row05[] = {"q2", " 1", "b", "b", "    q1", " 1", "N", " b", "N", " b", "N"}; 
const trow_t row06[] = {"q2", " b", "b", "b", "    q4", " b", "N", " b", "L", " b", "L"}; 
const trow_t row07[] = {"q3", " 0", "b", "b", "    q3", " 0", "R", " b", "N", " 0", "R"}; 
const trow_t row08[] = {"q3", " 1", "b", "b", "    q1", " 1", "N", " b", "N", " b", "N"}; 
const trow_t row09[] = {"q3", " b", "b", "b", "    q4", " b", "N", " b", "L", " b", "L"}; 
const trow_t row10[] = {"q4", " b", "0", "0", "    q4", " b", "N", " 0", "L", " 0", "L"}; 
const trow_t row11[] = {"q4", " b", "x", "x", "    q5", " b", "N", " x", "N", " x", "N"}; 

  sample.push_back(vector<string> (row01, row01 + sizeof (row01)/sizeof(*row01)));
  sample.push_back(vector<string> (row02, row02 + sizeof (row02)/sizeof(*row02)));
  sample.push_back(vector<string> (row03, row03 + sizeof (row03)/sizeof(*row03)));
  sample.push_back(vector<string> (row04, row04 + sizeof (row04)/sizeof(*row04)));
  sample.push_back(vector<string> (row05, row05 + sizeof (row05)/sizeof(*row05)));
  sample.push_back(vector<string> (row06, row06 + sizeof (row06)/sizeof(*row06)));
  sample.push_back(vector<string> (row07, row07 + sizeof (row07)/sizeof(*row07)));
  sample.push_back(vector<string> (row08, row08 + sizeof (row08)/sizeof(*row08)));
  sample.push_back(vector<string> (row09, row09 + sizeof (row09)/sizeof(*row09)));
  sample.push_back(vector<string> (row10, row10 + sizeof (row10)/sizeof(*row10)));
  sample.push_back(vector<string> (row11, row11 + sizeof (row11)/sizeof(*row11)));


  cout	<< endl;
  cout	<< space3
	<< string (setw10, '=')
	<< " "
	<< text1
	<< " "
	<< string (setw10, '=')
	<< endl;

  cout	<< space3
	<< string (setw12, '-')
	<< " "
	<< text2
	<< " "
	<< string (setw12, '-')
	<< endl;

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

  cout	<< space3 << string (setw10 + 1 + text1.size() + 1 + setw10, '=') << endl;

}

// =========