#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;
}// end dfa.cpp
