DFA-based text filter. Assume the language ? = {Ascii symbols including digits).

Question

DFA-based text filter.

Assume the language ? = {Ascii symbols including digits).

Construct a DFA which will accept the string 011 ( a representation for the number 3), and reject 101 ( a representation for number 5) and also reject strings 01i and fred.   (Let us call it Mod3 DFA).

Using the DFA, write a code in a high-level language C++ ( Visual Studio Professional 2010 C++),for this DFA.

Explanation / Answer

#include #include using namespace std; #define IS_A 0 #define IS_B 1 int main() { // We will need a table - it is nice if this table is a NxM where // M is the number of possible states (in this case 0 - 5) and // N is the number of possible chars in our alphabet // Each row should represent the current state and each transition. // so stateTable[1][0] is the transition from state 1 when the input is // the first char ('a' in this case) -- I made some macros above so we can use // stateTable[currentState][IS_A] to know what the transition is if we are in // "currentState" and the input as an 'a'. int stateTable[][2] = { {1, 1}, //state 0 (unused but using the place holder helps) {1, 2}, //state 1 (also stateTable[1]) {2, 3}, //state 2 etc. {4, 5}, {4, 4}, {5, 5}, }; // mark some special states int startState = 1; int endState = 4; int errorState = 5; //get an input string to test string testStr; cout > testStr; testStr = "aabaaaabaaaa"; // I just hard coded mine for now //initilize our FSM int currentState = startState; int index = 0; bool accepted = false; //begin to scan though chars... while(index

Related Questions

Navigate

• Browse (All)
• Browse D
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.