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.