In this project you will develop a program to simulate a given DFA.

Check for membership: Given as input the description of a DFA M (described below) and a string s, your program P returns Yes if M accepts s and No otherwise.

You can use any language you want.

You must provide a runTask.sh script that (compiles and) runs your program. This script allows the grader to run your code regardless of what language/compiler is used. So you might have your script call make and then run the compiled program on the rst argument to the script. E.g., all the grader has to run is ./runTask.sh dfa le input string.

/path/to/runTask.sh M1.dfa 01010101 Yes /path/to/runTask.sh M1.dfa 0101000 No /path/to/runTask.sh M1.dfa M1.dfa Yes

Specifications. The description of a DFA is given in a *.dfa text file and uses the format illustrated in the following example # This DFA recognizes { x in {0,1}* | x does not end in 000 } qe last bit was a 1 or non-existent # q0 la # g00 last three bits were 100 # g000 last three bits were 000 st two bits were 10 states: qe q00; qo input_alphabet 0; 1 start state: accept-states: qe; q0 ; q00 # accept as long as the last three bits weren't 000 # no last bit when we start # if we see a 1, reset: qe, 1-> qe; q0,1-> qe; q00, 1-> qe; q000, 1-> qe # if we see a 0, count one more 0 than before: qe ,0-> q0; q0,0-> q00 ; q00 ,0-> q000 # until we get to three, and then just remember: q000 ,0-) q000 #everything on one line q00,0 q000; q000,0 > q000 Specifications. The description of a DFA is given in a *.dfa text file and uses the format illustrated in the following example # This DFA recognizes { x in {0,1}* | x does not end in 000 } qe last bit was a 1 or non-existent # q0 la # g00 last three bits were 100 # g000 last three bits were 000 st two bits were 10 states: qe q00; qo input_alphabet 0; 1 start state: accept-states: qe; q0 ; q00 # accept as long as the last three bits weren't 000 # no last bit when we start # if we see a 1, reset: qe, 1-> qe; q0,1-> qe; q00, 1-> qe; q000, 1-> qe # if we see a 0, count one more 0 than before: qe ,0-> q0; q0,0-> q00 ; q00 ,0-> q000 # until we get to three, and then just remember: q000 ,0-) q000 #everything on one line q00,0 q000; q000,0 > q000