Overview

area: 0.0
The purpose of this mini-project is to make a connection between the theory of Finite State Machines (e.g. DFAs and NDFAs) and programming. It's very common for a program to have some notion of "state" and to react differently depending on that state. In designing such a program, making the "state" and the role it plays explicit makes it easier to build a system that functions correctly. This project involves a very simple (and admittedly rather pointless) GUI. When the user interacts with the GUI, an event message is generated. The system then has to take some action in response. The challenge is to determine what action to take in response to a message. Finite automata can help!

The Triangle App: The app (to the right) allows the user to play with triangles. The square with the picture in it is called the canvas. The button marked with T is the triChooseButton, and it brings up a dialogue box from which the user can choose different kinds of triangles. The button marked with R is the recenterButton. When the user clicks on the T button a clickTriChooseButton message is generated. The "brain" of the Triangle App might choose to respond to that event message with the showTP action, which makes the "Triangle Pane" visible (the Triangle Pane is essentially a pop-up menu). So the "brain" needs to simply read event messages and respond by writing action messages.
Checkout Triangle App Information.

Your Job: I've written the Triangle App GUI so that it writes GUI messages to a named pipe (fromGUI) as they occur, and responds to any action messages sent to a named pipe (toGUI) by changing what appears on the screen. Your job is to write a program that reads messages from fromGUI and responds with appropriate actions sent to toGUI.

Part 1 - Transducers



A transducer that reads in a string of the form $wc$, where $w \in \{a,b\}^*$, and outputs $w$ but with every $ab$ substring replaced with $ba$.
A DFA receives input, but never produces any output (unless you want to think of the accepting/non-accepting status of the state you end up in as being "output"). For controlling the GUI, things are different. Each GUI event message received is like an input symbol, and we are supposed to respond with an action(s), which is like an output symbol(s). This leads us to an extension or modification of the DFA model to what is called a transducer. In a transducer, each transition is labeled with an input symbol and an output string (which may, of course, be empty). There is no notion of accepting or rejecting, rather there is an input sequence of symbols and an output sequence of symbols. For our Triangle App problem, we have exactly this scenario: messages come in (like clickTriChooseButton) and actions go out (like showTP). So your first job is to develop a formal model for transducers. Note 1: for a transducer like the example to the right, any missing transition (like the $c$-transition out of state $q_0$) must be treated as a loop with no output. So for the example to the right, reading a $c$ in state $q_0$ would result in staying in $q_0$ and outputting nothing ($\lambda$).
Note 2: you are not allowed to look up information on transducers. The point is not whether you can copy down a definition from online or from some book. The point is to use what you've learned to develop your own formal models.
Note 3: Include in your solution the formal representation according to your development of the transducer in the example to the right.

Part 2 - A Transducer to control the GUI

The Triangle App Information page contains a detailed description of the Triangle App - what event-messages it sends and what action-messages it receives. A demo app is also there, so you can see how the program is supposed to act. You must duplicate that behavior! In this part, you must draw a transducer that reads event-messages and responds with the right action-messages to control the GUI. Your program will implement this trasducer, so think carefully about it!

Note: read through the event-messages and action-messages carefully! You'll notice from playing with the demo that, for example:

So you have to be thoroughly comfortable with how the GUI is supposed to act in all situations. If you are not sure, try it out in the demo. Whatever it does is "correct" behavior. If (somehow) there is still something that is not clear ... contact your instructor!

Part 3 - A GUI controller program

Finally, you have to write a program that implements your transducer in order to control the GUI. You can uses whatever language you like, but the source code and compilation instructions must be in the stuTriangleApp directory. Though when you submit you will only be submitting your files, not all the other stuff in the stuTriangleApp directory. We will grade by taking your code (as submitted via the cs submit system), compiling via your instructions, running via your instructions, all within a fresh copy of the stuTriangleApp directory. We will have two terminal windows, and we will first start your program in terminal 1, and second launch the GUI with 'npm start' in terminal 2.

Note 1: It is on you to test this. You will get no feedback from the submit system. The idea here is that if you are careful with your transducer design, the program really should work. Note that the transducer should help you test too, since it tells you what kind of inputs you need to test all possible transitions your program could make.
Note 2: Anything you write to cerr will not intefere with the GUI communication, which is through fromGUI and toGUI. That should help you with debugging!
Note 3: You must have a README file as one of your solution files that includes the names and alphas of your group members, instructions on how to compile your program, and instructions on how to run your program.

What to turn in

This "mini-project" will be done in groups of three (with special permission, group of two). You will submit the three parts as described above. There are three Milestones:
Rules: all three group members are expected to be present and contributing while working on each part. You cannot partition the parts and go off and work separately.
Honor
  1. For this assignment, work is intended to be done within the group only.
  2. For this assignment, you are allowed to discuss problems and solution strategies with folks from other groups. However, notes or any other record of what was discussed other than what's inside your brains must be destroyed when the discussion is finished, and you must wait at least 30 minutes before resuming work on your group's solutions, and you cannot look at other groups code or written work. Obviously, such discussions must be documented.
  3. You may not look up any information on transducers. The point is for you to formalize them for yourselves.
Grading: Look at this coversheet for information on how the project will be graded.

When and how to submit solutions

The project is due 2359 on 9 December 2024. However, if the electronic portion is submitted by 2359 on 10th it will be accepted, without penalty, as long as the paper material has been slid under your prof's office door by the time he arrives the next morning (the 11th).