// dfa.cpp simulate a Deterministic Finite Automata
//
// Machine definition of a DFA M = (Q, Sigma, alpha, q0, F)
// where Q is set of states
// Sigma is input tape alphabet
// alpha is transition table
// q0 is the starting state
// F is the set of final states
//
// Input Conventions:
//
// the file name extension is typically .dfa
// free form plain text input file
// typical execution is dfa < your_input.dfa > your_output.out
//
// A comment line has "// " as the first three characters
// A line may end with a comment using whitespace "//"
// Anything after whitespace after last expected input is a comment
//
// There are only a few keywords:
// start, final, halt, trace, limit, enddef and tape
// any line not starting with these keywords is a transition
// 'enddef' is only needed when more than one 'tape' is to be read
//
// there is no such thing as a continuation line
//
// A transition is a three tuple:
// from-state input-symbol to-state
//
// special input-symbol #b for the blank character,
// #e for epsilon transition
//
// at least one transition is required,
// the typical dummy transition is phi #b phi
//
// Anything after the required field(s) is a comment
//
// Use #b to input a blank (space) character on the input tape
// If you want a blank on the end of your tape, use your-stuff#b
// The initial position will point to your first tape character
// #] will be appended as a right_end character
// #[ will be appended as a left_end character
//
// Method: accumulate states, do consistency checking
// accumulate symbols, note any strangeness
// build transition map (note: duplicates means nondeterministic)
// run from start-state
// trace as user requests
// accept or reject (also halt feature)
//
// This is one of a series of automata simulators
// dfa deterministic finite automata (with epsilon transitions and halt)
// nfa nondeterministic finite automata
// tm Turing machine, deterministic (recognizer and function computation)
// ntm nondeterministic Turing machine (language recognizer only)
//
// compile with GNU g++ 2.8.1 or later or Microsoft 6.0 or later
// g++ -o dfa dfa.cpp or cl /GX /ML dfa.cpp
// ANSI/ISO C++
// release JSS 1/15/00 v1.0
// mod JSS 12/5/03 v1.1 fix bug found by g++ 3.2
#include <iostream.h>
#include <string.h>
#include <algorithm.h>
#include <vector.h>
#include <set.h>
#include <map.h>
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 #]
char buf[256]; // for printing comments in input file
// 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 lo
