Assignments and Evaluation

All students will be graded by the following components:

Assignment 1 5% Thursday, January 26th by start of tutorial session Gradescope
Assignment 2 5% Thursday, February 9th by start of tutorial session Gradescope
Assignment 3 5% Thursday, March 2nd by start of tutorial session Gradescope
Assignment 4 5% Thursday, March 23rd Thursday, March 30th by start of tutorial session Gradescope
Assignment 5 5% Thursday, April 6th by start of tutorial session Gradescope
Midterm test 25% Thursday, February 16th, During Tutorial Session Remote/online in OWL
Final Exam 50% Sunday, April 23rd, 10am-12pm. Alumni hall AH15, in person

Assignment Formatting Requirements

You must use a software tool for any diagrams involving automata. Hand-drawn automata diagrams will not be accepted.

How to draw Finite State Machines

There are several options for drawing automata in software. Here are two.

Option 1: LaTeX with TiKZ

LaTeX is a typesetting markup language. It has a bit of a learning curve, but if you want to produce documents like a real computer scientist or mathematician, this is for you.

If you don't want to install LaTeX on your local machine, Overleaf provides a cloud-based interface, and is a common choice for many graduate students.

TiKZ is a LaTeX package for drawing diagrams. Here's a good tutorial on how to draw automata.

Option 2: Graphviz Online Editor

If you want the "easy-button" option, the online Graphviz editor is for you.

Here's an example of a deterministic finite automaton on the alphabet {0,1} that accepts all strings that contain one or more 1's:

digraph finite_state_machine {
node [fontname="Helvetica,Arial,sans-serif"]
edge [fontname="Helvetica,Arial,sans-serif"]
rankdir=LR;

#Define final/accepting states
node [shape = doublecircle]; b;
node [shape = circle];

#Define initial state
start -> a;

#Define state transitions
a -> a [label = "0"];
a -> b [label = "1"];
b -> b [label = "0,1"];
}