CS 5010: Problem Set 02
Out: Monday, 23 January 2017
Due: Monday, 30 January 2017 at 6pm
This is an individual assignment. You are not allowed to discuss this problem set with any other person. You are also not allowed to search for or to view any solutions to similar problems that may be available on the World-Wide Web or in other resources that might otherwise have been available to you.
The main purpose of this problem set is to give you practice with data design and with functions that operate on scalar and itemization data.
You must use Racket's HtDP Beginning Student Language for this problem set.
For these problems, download a copy of extras.rkt and put it in the folder with your solutions. Then import this library by including the line
at the top of your file with the other
declarations. Then, for each problem, put in lines that say
for each deliverable function. Thus, for problem 1, the top
q1.rkt file should say
(require rackunit) (require 2htdp/universe) ; needed for key=? (require "extras.rkt") (provide make-editor editor-pre editor-post editor? edit)
This will allow our testing framework to import your file and do automated testing on it.
Remember that you must follow the design recipe, which is a process, not a list of deliverables. Your deliverables include the artifacts produced by the various steps of the design recipe: data definitions (including interpretation and templates, contracts, purpose statements, definitions, and tests). Be sure to follow our coding conventions. Doing so will make codewalks easier for everyone.
Be sure to fill out a
work session report
at the end of each work session.
git to add it to the files you will commit,
and then commit and push (sync) that report in addition to
committing and pushing your entire
Do this at the end of every work session.
Remember to include a copy of
set02 directory, as well as your
(Tiny Test Editor)
Do exercise 84 (the function "edit") from Part I, section 5.10 of HtDP/2e.
You are to write a file called
q1.rktthat provides the following functions:
make-editor editor-pre editor-post editor? edit
For this problem, we will consider
KeyEventto be a scalar data type, which can be decomposed using the cases strategy.
key=?are defined in the
2htdp/universemodule. Look in Racket's Help Desk for details. To import
key=?, you will need to
We will be doing automated testing of your solution, so be sure your solution is in the right place (
set02/q1.rktin your private
cs5010sp17/pdp-YOURUSERNAMErepository), and that it provides all the functions listed above. To see if your file is in the right place, insert the following line somewhere near the top of your file:
(check-location "02" "q1.rkt")
(Finite State Machine)
This exercise is loosely based on Exercise 109 in HtDP/2e, but you will NOT create any displays.
As in Exercise 109, you are to design a finite-state machine and a set of functions that illustrate the workings of that machine. The machine you design will accept a sequence of letters (with each letter represented as a
1String) if and only if that sequence matches the regular expression
(d* | d* p d* | s d* | s d* p d*) (d | d e)
sdddeall match that regular expression, but the sequences
Your program must define two data types,
LegalInputdata type consists of the four one-letter strings that represent a legal second argument to your
"e". You do not need to give an interpretation for each
LegalInput, because the problem makes sense even if the inputs are uninterpreted. (You might be interested to know, however, that this problem is related to the syntax of numerical constants in many programming languages.)
To design your
Statedata type, you will need to design your finite state machine as part of your information analysis and data design. Your information analysis and design should produce a state-transition diagram (like the ones here) that shows the meaning of your machine states. Your data design should also include an interpretation for each state. Make your state-transition diagram as simple as you can, and submit a picture of it in JPEG or PNG format as a separate file named
q2.png. You can create this file using a graphics program or by drawing your state transition diagram on a piece of paper and taking a good picture of it.
After you have done your data design, use your design to design and
providethese four functions:
initial-state : Number -> State GIVEN: a number RETURNS: a representation of the initial state of your machine. The given number is ignored. next-state : State LegalInput -> State GIVEN: a state of the machine and a machine input RETURNS: the state the machine should enter if it is in the given state and sees the given input. accepting-state? : State -> Boolean GIVEN: a state of the machine RETURNS: true iff the given state is a final (accepting) state rejecting-state? : State -> Boolean GIVEN: a state of the machine RETURNS: true iff there is no path (empty or non-empty) from the given state to an accepting state
Please note that some of your machine's states are likely to be neither accepting nor rejecting.
Remember that we will be doing automated testing of your solution, so be sure your solution is in the right place (
set02/q2.rktin your private
cs5010sp16/pdp-YOURUSERNAMErepository), and that it provides all the functions listed above. To see if your file is in the right place, insert the following line somewhere near the top of your file:
(check-location "02" "q2.rkt")