On this assignment, you will create DFAs for certain regular languages, write a tool that determines if a DFA recognizes a string, then extend this tool to a

Simplified Maximal Munch scanner.

You will write DFAs in the cs$241$ DFA file format, and you will use the cs$241.$DFA tool to test your DFAs in problems $1$ and $2,$ and optionally in problems $3,$

$4,$ and $5.$

The cs$241.$DFA $($web version$)$ tool reads a DFA file and for a given test input $($specified in the DFA file$),$ the DFA tool tests the input against the DFA.

You will submit your solutions to Marmoset, which will run your solution against some automated tests. Each problem specifies a required filename that you

must use for your Marmoset submission.

Note: From this problem onwards for the remainder of the course, when an assignment uses the description "release$+$secret", what this means is that release

tests are worth no marks, but each release test has a similar $($but not identical$)$ secret test which is worth marks. The goal of release$+$secret testing is to

ensure that you test for yourself and don't overspecialize to our test cases. When marks are described just as "secret", this means that there are secret test

cases which are unrelated to release tests, and you must consider the full range of testing possibilities on your own for such marks, with no feedback.

Problem $1$: Alfalfa $[1$ mark of $10$: $1$ public$]($filename: alfalfa.dfa$)$

Write a DFA with the alphabet $\{$a$,$ l$,$ f$\}$ recognizing the language of strings that contain the string "alfalfa".

DFAs are specified in the course specific DFA file format we have created for the course.

Extra Practice Problems

Here are some extra optional problems if you would like more practice with DFAs. You can submit the following files to A$2$P$1$ on Marmoset, and Marmoset

will check that your DFA is correct.

These problems are not worth marks. There is no bonus for completing them.

catstar.dfa: Construct a DFA with alphabet $\{$a$,$c$,$t$\}$ recognizing the language described by the regular expression $($ca$($a$)*$t$)*.$

cattac.dfa: Construct a DFA with alphabet $\{$a$,$c$,$t$\}$ recognizing strings that do not start or end with a$,$ and for every a in the string, the letter before

the a is different from the letter after the a$.$

endalfalfa.dfa: Construct a DFA with alphabet $\{$a$,$ l$,$ f$\}$ recognizing the language of strings that end with alfalfa.

Submit all DFA files together in a zip file. If you submit only one, Marmoset will still run the tests but you will only get marks for the one you submitted.

Problem $2$: $-64$ to $512[1$ mark of $10$: $0$ public $/1$ release$]($filename: $64-$to$-512.$dfa$)$

Write a DFA with the alphabet $\{-,0,1,2,3,4,5,6,7,8,9\}$ that recognizes the language of integers made of numeric characters $($optionally started

with a negative sign$),$ between the range $-64$ and $512($inclusive$),$ with no leading $0$s$,$ and no negative $0($i$.$e$."-0")$

Problem $3$: DFA Recognizer $[2$ marks of $10$: $1$ public $/1$ release$+$secret$]($filename: dfa.c$($c$|$pp$)$ or

dfa.rkt$)$

Write a program that reads a DFA file from standard input, and for each string in the input section of the file, determine whether the string is accepted by the

DFA. Print a single line of output $($to standard output$)$ for each string:

If the string is accepted, print the string, followed by a space, followed by true

If the string is not accepted, print the string, followed by a space, followed by false

To simplify your task, starter code is provided that reads a DFA file from standard input. The starter code does not actually do anything, but comments are

provided at the locations where the code has finished reading certain pieces of information. You should fill in these sections with your own code that sets up

appropriate data structures and implements the DFA recognition algorithm.

c$++$: dfa.cpp

racket: dfa.rkt

If you use the c$++$ starter code, you can compile the code with:

g$++-$g $-$O$0-$fPIC $-$std$=$gnu$++20-$Wall $-$Wextra $-$pedantic$-$errors $-$Wno$-$unused$-$parameter $-$o dfa dfa.cpp

And run the code with:

$./$dfa $<$ input.dfa

If you use the racket starter code, you can run the code with:

racket dfa.rkt $<$ input.dfa

You are not required to use the starter code, and you are allowed to change the starter code in any way you see fit. However, the starter code does not

purposefully contain any bugs or issues that will cause you to lose marks on this assignment. We strongly recommend that you use the starter code.

Note that the DFA file format uses the special keyword $.$EMPTY to denote the empty string. If $.$EMPTY is given as input, then in your output, you should print

$.$EMPTY $($rather than nothing$).$

Your program does not need to check errors in the DFA file. Each DFA file in the tests follows the DFA file format, and the specified DFA is a valid DFA.

Note that inputs in the $.$INPUT section are not a part of the definition of DFA.

Your program should behave the same as the cs$241.$DFA tool aside from error checking $($cs$241.$DFA does error checking, but you do not need to$).$

FFixed an