0

Problem statement:

The program has to take input for DFA and for h() function that is for homomorphism.

I am able to write the program in C++ only for DFA. I am unable to include the h() function.
Moreover, my DFA program giving me an error.

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
using namespace std;

  class transition // an entry in 'alpha' transition_table 
  {
    public:
      transition(string from_state,
                 char   input_symbol,
                 string to_state)
                 {from=from_state;
                 input=input_symbol;
                 to=to_state;}
      static bool smaller(transition a, transition b)
                     { if(a.from<b.from) return true;
                       else if(a.from>b.from) return false;
                       else return a.input<b.input; }
      friend ostream &operator<<(ostream &stream, transition trans);
      string from;
      char   input;
      string to;
  };
  

int main() //  dfa < input-file > output-file
{
  // primary objects
  set<string>  states;         // Q =all named states
  set<string>  from_states;    // source states for checking
  set<string>  to_states;      // target states for checking
  string       start = "";     // q0 = starting state
  set<string>  final;          // F = set of final states
  set<char>    symbols;        // Sigma = set of tape symbols
  set<string>  trace;          // states to trace
  vector<char> tape;           // input tape
  vector<transition> t_table;  // alpha = transition table
  typedef pair<string, int> c_index; // to make t_index 
  map<string, int, less<string> > t_index; // t_table index
  
  // primary iterators  
  vector<transition>::const_iterator x;      // for t_table
  int tx;                                    // for t_table
  set<string>::const_iterator        iter;   // for sets
  set<string>::const_iterator        iter2;  // for sets
  vector<char>::iterator             it;     // for tape
  string::iterator                   its;    // for string
  
  // control variables
  int limit = 10000;        // max number of transitions (user settable)
  int step;                 // transition step
  bool halt_mode = false;   // stop upon entering a 'final' state
  bool accepted = false;    // reached a final state and input right-end
  bool no_simulate = false; // set true by various errors
  string state;             // present state
  int tape_position;        // tape position
  char input_char = ' ';    // tape character read
  string next_state = " ";  // transition to next state
  int i;                    // loop index
  string prev_from = " ";   // for detecting nondeterministic
  char prev_input = ' ';    // for detecting nondeterministic
  bool have_enddef = false; // may have to read "tape"
  bool nondeterministic = false; // use nfa simulator, not this dfa
  
  // input variables
  string keyword;          // for inputting candidate keyword
  string from_state;       // for inputting one from_state
  string input_symbol;     // character extracted later
  string to_state;         // for inputting one to-state
  string final_state;      // for inputting one final or halt state
  string trace_state;      // for inputting one trace_state
  string initial_tape =""; // check for #b (may read more than 1)
  string check;            // check for // that ends data on a line
  string input_str;        // temp string for #]
  
  // keywords and special symbols
  string key_start = "start";  // followed by a state
  string key_tape  = "tape";   // followed by a string, may have #b
  string key_final = "final";  // followed by a final state name
  string key_halt  = "halt";   // followed by a final state name, halt mode
  string key_trace = "trace";  // followed by "all" or a state
  string key_limit = "limit";  // followed by an integer
  string key_enddef= "enddef"; // only a "tape" may follow this
  string comm      = "//";     // start comment
  string empty     = "";       // empty string
  char epsilon   = '\0';       // unprintable, #e epsilon
  char right_end = '\1';       // unprintable, #] off right end of tape
  char left_end  = '\2';       // unprintable, #[ off left end of tape
  
  cout << "dfa v1.1 starting" << endl;

  while(!cin.eof()) // main input loop
  {
    cin >> keyword;
    if(cin.eof()) break;
    if(keyword==key_start)
    {
      if(start!=empty) cout << "Over writing a previous start state."
                            << endl;
      cin >> start;
      states.insert(start);
      if(start=="//") cout << "start looks like a comment?" << endl;
      cin.ignore(255,'\n');
      continue;
    }
    else if(keyword==key_tape)
    {
      cin >> initial_tape;
      if(initial_tape=="//") initial_tape="";
      cin.ignore(255,'\n');
      continue;
    }
    else if(keyword==key_final)
    {
      cin >> final_state;
      final.insert(final_state);
      if(final_state=="//") cout << "final looks like a comment?" << endl;
      cin.ignore(255,'\n');
      continue;
    }
    else if(keyword==key_halt)
    {
      halt_mode = true; // halt upon entering any final state
      cin >> final_state;
      if(final_state!=comm && final_state!=empty)
      {  // allow stand alone "halt" just to set flag
        final.insert(final_state);
      }
      cin.ignore(255,'\n');
      continue;
    }
    else if(keyword==key_trace)
    {
      cin >> trace_state;
      trace.insert(trace_state);
      if(trace_state=="//") cout << "trace state looks like a comment?" << endl;
      cin.ignore(255,'\n');
      continue;
    }
    else if(keyword==key_limit)
    {
      cin >> limit;
      cin.ignore(255,'\n');
      continue;
    }
    else if(keyword==key_enddef) // stop inputting
    {                            // now may only read "tape"
      cin.ignore(255,'\n');
      have_enddef = true;
      break;
    }
    else if(keyword=="//") // skip comment "// "
    {
      cin.ignore(255,'\n');
      continue;
    }
    else
    {
      from_state = keyword;
      states.insert(from_state);
      from_states.insert(from_state);
    }
    cin >> input_symbol; if(cin.eof()) break;
    if(input_symbol=="#b") input_symbol[0]=' ';        // a space
    if(input_symbol=="#e") input_symbol[0]=epsilon;    // epsilon
    if(input_symbol=="#]") input_symbol[0]=right_end;  // right end
    
    cin >> to_state;     if(cin.eof()) break;
    states.insert(to_state);
    to_states.insert(to_state);
    cin.ignore(255,'\n'); // delete trailing comments
    t_table.push_back(transition(from_state, input_symbol[0], to_state));
    
  } // end main input loop

  cout << "reading input finished." << endl;

  // print primary data objects, check for errors and warnings
  if(states.size()==0)
  {
    cout << "No states input prevent simulation. Stopping." << endl;
    return 1;
  }

  cout << "start state " << start << endl;

  cout << "states:";
  for(iter=states.begin(); iter!=states.end(); iter++) cout << *iter << " ";
  cout << endl;

  iter = from_states.find(start); // check that start is a legal state
  if(iter==states.end())
  {
    cout << start << " is not a legal starting state." << endl;
    no_simulate=true;
  }
  cout << endl;
  
  cout << "final states:";
  if(final.size()==0)
  {
    cout << "   No final states" << endl;
  }
  else if(to_states.size()!=0)
  {
    for(iter=final.begin(); iter!=final.end(); iter++) cout << *iter << " ";
    cout << endl;

    for(iter=final.begin(); iter!=final.end(); iter++) // check final states
    {
      iter2 = to_states.find(*iter);
      if(iter2==to_states.end() && (*iter!=start))
      {
        cout << *iter << " is not a valid final state." << endl;
        no_simulate=true;
      }
    }
    cout << endl;
  }

  if(trace.size()==1 && *trace.begin() == "all") trace = states;
  cout << "trace states:";
  if(trace.size()==0)
  {
    cout << "No states to trace" << endl;
  }
  else
  {
    for(iter=trace.begin(); iter!=trace.end(); iter++) cout << *iter << " ";
    cout << endl << endl;

    for(iter=trace.begin(); iter!=trace.end(); iter++) // check trace states
    {
      iter2 = states.find(*iter);
      if(iter2==states.end())
      {
        cout << *iter << " is not a valid trace state." << endl;
      }
    }
    cout << endl;
  }

  if(t_table.size()!=0)
  {
    t_table.push_back(transition("", epsilon, "")); // error catching node
    sort(t_table.begin(), t_table.end(), transition::smaller );
    cout << "Sorted transition table:" << endl;
    for(x=(t_table.begin()+1); x!=t_table.end(); x++)
    {
      cout << *x << endl;
      if(x->from==prev_from && (x->input==prev_input ||
         prev_input==epsilon))
      {
        nondeterministic = true;
        cout << "                            duplicate transition" << endl;
      }
      prev_from=x->from;
      prev_input=x->input;
    }
  }
  else
  { 
    cout << "No transitions (three tuples)" << endl;
    no_simulate=true;
  }

  if(nondeterministic)
  {
    cout << "nondeterministic 'alpha' transition table" << endl;
    cout << "either eliminate duplicate transitions or use nfa simulator"
         << endl;
    return 1;
  }
  if(no_simulate)
  {
    cout << "Errors in input prevent simulation. Stopping." << endl;
    return 1;
  }

  // build map for state+input_character to transition table index
  for(tx=0; tx<t_table.size(); tx++)
  {
    t_index.insert(c_index(t_table[tx].from+t_table[tx].input, tx));
  }
  

  // main simulation loop for each tape
  do // may read zero or more "tape" lines
  {
    if(initial_tape.size()==0 && have_enddef) // expect to read a "tape"
    {
      cin >> keyword; // only "tape" is allowed
      if(!cin.eof() && keyword==key_tape)
      {
        cin >> initial_tape;
        if(initial_tape=="//") initial_tape = ""; // null tape
        cin.ignore(255,'\n');
      }
      else
      {
        cout << " No more input tapes. Stopping." << endl;
        return 1;
      }
    }
    
    // clean up initial_tape into tape
    tape.clear(); // may come around again
    tape.push_back(left_end); // force known beginning of tape
    for(its=initial_tape.begin(); its!=initial_tape.end(); its++)
    {
      if((its+1)!=initial_tape.end())
      {
        if(*its=='#' && *(its+1)=='b')
        {
          tape.push_back(' ');
          its++;
        }
        else
        {
          tape.push_back(*its); // allows '#' sometimes    
        }
      }
      else
      {
        tape.push_back(*its);        
      }
    }
    tape.push_back(right_end); // force known end of tape
    tape_position = 1; // start past #[ on first user character
    cout << endl << "tape = ";
    for(it=(tape.begin()+1); it!=(tape.end()-1); it++) cout << *it;
    cout << endl; // do not print the left_end and right_end
  
    state=start;          // state set to next_state at bottom of loop
    input_char = tape[tape_position]; // input_char set also at bottom
    for(step=1; step<limit; step++)
    {
      if(trace.size()!=0 && trace.find(state)!=trace.end())
      {
        input_str = input_char;
        if(input_char==right_end) input_str = "#]";
        cout << "step " << step << "  " << state << "  "
             << input_str << " at pos " << tape_position << endl;
        cout << "tape=";
        for(it=(tape.begin()+1); it!=(tape.end()-1); it++) cout << *it;
        cout << endl;
        cout << "     ";
        for(i=0; i<tape_position; i++) cout << ' ';
        cout << '^' << endl;
      }
  
      // check for termination
      if(final.size()!=0 && final.find(state)!=final.end())
      {
        if(input_char==right_end)
        {
           accepted = true;
           break; // out of 'step' loop
        }
        else if(halt_mode)
        {
           accepted = false;
           break; // out of 'step' loop
        }
      }
      if(input_char==right_end)
      {
         accepted = false;
         break; // out of 'step' loop
      } // continue if no termination
  
  
  
      // finally do a transition, test for epsilon transition first
      tx = t_index[state+epsilon];   // won't throw exception on no find
                                     // thus created dummy transition at tx==0
      if(tx==0)
      {
        // pull up next normal transition
        tx = t_index[state+input_char]; // won't throw exception on no find
                                     // thus created dummy transition at tx==0
        tape_position++;
      }
 
      if(tx==0) // transition not found, error catch entry found
      {
        cout << "No next transition, quitting now" << endl;
        // not finished, not accepted
        break; // out of 'step' loop
      }

      next_state=t_table[tx].to;
       
      if(trace.size()!=0 && trace.find(next_state)!=trace.end())
      {
        cout << "transition to state=" << next_state << endl;
      }
  
  
      if(tape_position>=tape.size()) // bug catcher, should not happen
      {
        break; // out of 'step' loop, no more input
      }
      
      state=next_state;
      input_char = tape[tape_position];
    } // step limit loop, go for next transition
  
  
    // final messages to the user
    if(accepted)
    {
      cout << "tape accepted after " << step << " steps, at " 
           << state << endl ;
    }
    else
    {
      cout << "tape rejected after " << step << " steps, at "
           << state << endl;
    }
    initial_tape = "";
    accepted = false;
  
  }while(!cin.eof() && have_enddef); // close out tape read 'do'

  return 0;
} // end of main

// for outputting objects of class  transition
ostream &operator<<(ostream &stream, transition trans)
{
  string input_token=string(1,trans.input);
  if(trans.input=='\0') input_token=string("#e");
  if(trans.input=='\1') input_token=string("#]");
  if(trans.input=='\2') input_token=string("#[");
  
  stream << trans.from  << '\t' 
         << input_token << '\t'
         << trans.to    << '\t' ;   
  return stream;
}

Please do correct my code, and if you are able to execute this program, please let me know how did u execute and please please help me in including the h() function. If you have any questions please feel free to ask me.

Looking forward for your reply.

Thanking you in advance.

1
Contributor
1
Reply
2
Views
8 Years
Discussion Span
Last Post by cute121180
0

To be more specific and understandable i am posting the actual question

Assume that we have a function h: {0,1}  {a,b}* (e.g. h(0) = ab, h(1) = bba. Then we can define h(01) = h(0).h(1) = abbba).
Let R be a regular language under {a,b}*, one can show that the set h-1 (R)
= w| h (w)  R is also regular.
Write a program that take the input of a function h together with a DFA (with alphabet {a,b}), and generate a DFA that recognize h-1 (R)
Rules to Follow:
You can define the format for the DFA. You should read the DFA in from a file.
You should be able to deal with the DFA with an arbitrary number of sets.

This is the actual question

Please do help me.
I am need of it.
This program is my life saver.


Thanking you in advance.

This topic has been dead for over six months. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.