Question 4

Deadline	Friday, September 29, 11:59pm
Name on Marmoset	Q4A, Q4B
To Submit	Q4A: `alfalfa.dfa` Q4B: `numbers.dfa`
Marking Scheme	Q4A: 50% Q4B: 50%

Two DFAs

In this question, you will create two DFAs using a custom DFA file format we have created for the course. You can test your DFAs using the cs241.DFA tool.

Part A: Alfalfa (50% of question mark)

Create a DFA that recognizes strings that end with alfalfa and do not contain characters other than the letters a, l, and f.

Input Example

If you add the following input sections to the end of your alfalfa.dfa file:

.INPUT
alfalfa
.INPUT
fallfalfa
.INPUT
falalfalfa
.INPUT
You got the alfalfa
.INPUT
alfalfalfalfalfalfa

Then if your DFA is correct, the output from cs241.DFA should be:

cs241.DFA < alfalfa.dfa
alfalfa: true
fallfalfa: false
falalfalfa: true
You got the alfalfa: false
alfalfalfalfalfalfa: true

You do not need to remove the .INPUT sections from your file before submitting. As long as there is not a syntax error in these sections, Marmoset will ignore them.

Part B: Numbers (50% of question mark)

Create a DFA that recognizes strings representing decimal numbers in the range -128 to 255.

A valid string can optionally start with a negative sign (-), and otherwise can only consist of digit characters (0 to 9).
Useless leading zeroes are not allowed. In other words, zero is represented by the single character 0, and no other numbers can start with 0.
The string -0 (negative zero) is not allowed.
The value of the number must be between -128 and 255, inclusive.

Input Example

If you add the following input sections to the end of your numbers.dfa file:

.INPUT
0
.INPUT
123
.INPUT
241
.INPUT
-123
.INPUT
-241
.INPUT
256
.INPUT
1000
.INPUT
-0

Then if your DFA is correct, the output from cs241.DFA should be:

cs241.DFA < numbers.dfa
0: true
123: true
241: true
-123: true
-241: false
256: false
1000: false
-0: false

You do not need to remove the .INPUT sections from your file before submitting. As long as there is not a syntax error in these sections, Marmoset will ignore them.