n class, we developed pseudocode for a DFA evaluator: string alpha = "a b c"; int state_cnt = 4; int start = 1; bool final[] = {F,T,F.T,F}; int cur = start; char *s = "abaab"; //This is used somewhere in code if(final[cur]); int trans[state.cnt +1][alpha.length()] = { {0,0,0}, {2,0,2}, {0,3,2},{1,0,4},{3,1,3}} while(*s != '10' && cur != 0}{ cur = trans[cur][alpha.find(*s)]; s++; } Write a C++ program to read a DFA's details from a file provided as a command line argument (not a prompt where the user is asked to type a filename) and determine whether each provided string is in its language. The DFA file is formatted as a number of lines: Line 1: number of states (eg, 7 indicates states 1-7 along w/ state 0, the "no-transition" state) Line 2: initial state Line 3: the final states as a space separated list Line 4: alphabet string (each character is a member of the alphabet) Line 5 begins the transition table, one line for each state starting with state 1. Each line is a list of space separated integers indicating to which state to transition on a character from the alphabet Afterward, each line is a non-empty string of characters from the alphabet to validate against the DFA. If the line is blank, assume that means the empty string. Please note that "blank" lines still have a newline character sequence at the end… just don't want you to mistake a newline at the end of a file as a blank line. For example, the file on the right details the DFA from the table on the left… 7 1 3 7 ab 3 4 2 5 0 0 5 7 1 2 4 3 1 0 abaa a baab bbbbaaaa aba baabb The output of the program should be one line for each of the test strings in the DFA file. Each line should begin with "good" or "bad " indicating the string is or is not, respectively, accepted by the DFA. After this is an additional space followed by the test string. The exact output for the example DFA file above is… bad abaa good a bad baab bad bad bbbbaaaa bad aba good baabb
In class, we developed pseudocode for a DFA evaluator:
string alpha = "a b c";
int state_cnt = 4;
int start = 1;
bool final[] = {F,T,F.T,F};
int cur = start;
char *s = "abaab";
//This is used somewhere in code
if(final[cur]);
int trans[state.cnt +1][alpha.length()] = { {0,0,0}, {2,0,2}, {0,3,2},{1,0,4},{3,1,3}}
while(*s != '10' && cur != 0}{
cur = trans[cur][alpha.find(*s)];
s++;
}
Write a C++ program to read a DFA's details from a file provided as a command line argument (not a prompt where the user is asked to type a filename) and determine whether each provided string is in its language.
The DFA file is formatted as a number of lines:
-
Line 1: number of states (eg, 7 indicates states 1-7 along w/ state 0, the "no-transition" state)
-
Line 2: initial state
-
Line 3: the final states as a space separated list
-
Line 4: alphabet string (each character is a member of the alphabet)
-
Line 5 begins the transition table, one line for each state starting with state 1. Each line is a list of space separated integers indicating to which state to transition on a character from the alphabet
-
Afterward, each line is a non-empty string of characters from the alphabet to validate against the DFA. If the line is blank, assume that means the empty string. Please note that "blank" lines still have a newline character sequence at the end… just don't want you to mistake a newline at the end of a file as a blank line.
For example, the file on the right details the DFA from the table on the left…
|
7 1 3 7 ab 3 4 2 5 0 0 5 7 1 2 4 3 1 0 abaa a baab bbbbaaaa aba baabb |
The output of the program should be one line for each of the test strings in the DFA file. Each line should begin with "good" or "bad " indicating the string is or is not, respectively, accepted by the DFA. After this is an additional space followed by the test string.
The exact output for the example DFA file above is…
|
bad abaa good a bad baab bad <empty> bad bbbbaaaa bad aba good baabb |
Trending now
This is a popular solution!
Step by step
Solved in 3 steps with 1 images
