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

      (require "extras.rkt")
    

at the top of your file with the other require declarations. Then, for each problem, put in lines that say

      (provide function)
    

for each deliverable function. Thus, for problem 1, the top of your 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. Tell 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 set02 directory. Do this at the end of every work session.

Remember to include a copy of extras.rkt racket in your set02 directory, as well as your q2.jpg or q2.png file.

---

1. (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.rkt that provides the following functions:

             make-editor
             editor-pre
             editor-post
             editor?
             edit
           

   For this problem, we will consider KeyEvent to be a scalar data type, which can be decomposed using the cases strategy. KeyEvent and key=? are defined in the 2htdp/universe module. Look in Racket's Help Desk for details. To import key=?, you will need to require 2htdp/universe.

   We will be doing automated testing of your solution, so be sure your solution is in the right place (set02/q1.rkt in your private cs5010sp17/pdp-YOURUSERNAME repository), 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")
           

2. (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)
           

   The sequences d, dd, sd, ddddpdd, and sddde all match that regular expression, but the sequences ddddp, and spe do not.

   Your program must define two data types, LegalInput and State.

   The LegalInput data type consists of the four one-letter strings that represent a legal second argument to your next-state function: "d", "p", "s", and "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 State data 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.jpg or 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 provide these 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.rkt in your private cs5010sp16/pdp-YOURUSERNAME repository), 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")