1. Create a new program called DFA_Alphabet and modify the code provided below t
ID: 3808200 • Letter: 1
Question
1. Create a new program called DFA_Alphabet and modify the code provided below to take any alphabet as input. For example, the new alphabet could be "ab", "xy", "01", etc.
2. Create a new program called DFA_Complement to accept the complement strings of DFA_Alphabet above. In other words, DFA_Complement will accept any strings not starting with "ab", and accepts the rest, if your alphabet is on "ab".
PLEASE NOTE: the program must provide a reusable simulation, that is, do not simply hard code it to only accept certain strings.
#include
#define NSTATES 4 //defines NSTATES as an alias for the number 4 (the number of states in our DFA)
#define NCHARS 2 //defines NCHARS as an alias for the number 2 (the number of characters in our alphabet)
#define NACCEPTS 1 //defines NACCEPTS as an alias for the number of accept states in our DFA
int L[NSTATES][NCHARS]={{1,3},{3,2},{2,2}, {3,3}}; //creates a 2 dimensional array to represent our states and transitions.
int ACCEPTS[NACCEPTS]={2}; //creates an integer array of our accept states, of which there is only one
main()
{
int state,ch,i; //declare 3 variables to hold our state, the next character read from input, and a counter
for (state=0; (ch=getchar())!= -1&&ch!=' ' && ch!=' ';state=L[state][i]) //continue looping as long as the next character read from the file isn't the end of a line or a space. After each iteration, update the current state depending on the last digit read from input
{
i=ch-'0';
} //read the next digit from input
for(i=0;i if(ACCEPTS[i]==state) //check if the final is an accept state
{printf("yes ");return(0);} //print "yes" if the final stal state is an accept state
printf("no "); //otherwise, print no
return(0); //exit the program
}
Explanation / Answer
#include<stdio.h>
#define NSTATES 4 //defines NSTATES as an alias for the number 4 (the number of states in our DFA)
#define NCHARS 2 //defines NCHARS as an alias for the number 2 (the number of characters in our alphabet)
#define NACCEPTS 1 //defines NACCEPTS as an alias for the number of accept states in our DFA
int CHARS[NCHARS];
int L[NSTATES][NCHARS]={{1,3},{3,2},{2,2}, {3,3}}; //creates a 2 dimensional array to represent our states and transitions.
int ACCEPTS[NACCEPTS]={2}; //creates an integer array of our accept states, of which there is only one
DFA_Alphabet()
{
int state,ch,i; //declare 3 variables to hold our state, the next character read from input, and a counter
for (state=0; (ch=getchar())!= -1&&ch!=' ' && ch!=' ';state=L[state][i]) //continue looping as long as the next character read from the file isn't the end of a line or a space. After each iteration, update the current state depending on the last digit read from input
{
for (i=0;i<NCHARS; i++)
if (CHARS[i] == ch)
break;
} //read the next digit from input
for(i=0; i<NACCEPTS; i++)
if(ACCEPTS[i]==state) //check if the final is an accept state
{
printf("yes ");
return(0);
} //print "yes" if the final stal state is an accept state
printf("no "); //otherwise, print no
return(0); //exit the program
}
DFA_Complement()
{
int state,ch,i,flag = 0; //declare 3 variables to hold our state, the next character read from input, and a counter
for (state=0; (ch=getchar())!= -1&&ch!=' ' && ch!=' ';state=L[state][i]) //continue looping as long as the next character read from the file isn't the end of a line or a space. After each iteration, update the current state depending on the last digit read from input
{
for (i=0;i<NCHARS; i++)
if (CHARS[i] == ch)
break;
} //read the next digit from input
for(i=0; i<NACCEPTS; i++)
if(ACCEPTS[i]==state) //check if the final is an accept state
{
flag = 1;
break;
} //set flag if the final stal state is an accept state
if (flag==1)
printf("no "); //no if final state is found in the accept state(s) of the original DFA
else
printf("yes ");//otherwise, print yes
return(0); //exit the program
}
void init(char *alphabets) { // To initialize the alphabets
int i=0; // Call from main before any other operation
for (;i<NCHARS; i++)
CHARS[i]=alphabets[i];
}
void main(){
void init(char *);
/* init("ab");
OR
init("01");
OR
init("XY"); etc
*/
}
I made the following changes:
1. Introduced two methods one for DFA_Alphabet other for DFA_complement
2. Introduced third method to initialize the input alphabets, you may call it from main or even from DFA_Alphabets or DFA_Complement
3. Changed the way input character is interpreted inside the for loop of both functions.
In case of difficulties, please feel free to comment below.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.