Textbook and supplies
The required textbook for this course is
Sipser, Michael
Introduction to the Theory of Computation
I highly recommend this book for the class - it's very well-written and we'll be using it extensively.
Due to the current global situation, the textbook publisher is offering free access to the electronic version of this book for this quarter. To get access,
you need to create an account with them (you only have to do this once) and select "Start Free Trial". In two weeks, you will need to renew the free trial; they've set it up so you can continually renew free access through end of this term. Here are more details from Cengage:
- For students who have purchased Cengage Unlimited, they can continue to use Cengage Unlimited with no interruption in service, and we will extend access as needed, based on the situation at your institution (i.e. more days are added to your spring semester). For these students, there is no action item at this time.
- For students who are not currently using Cengage Unlimited and have not otherwise activated a trial with us within the last 75 days, they should go to www.cengage.com, create an account with us, and choose "Start Trial".
Here is a link to help you with the process: https://www.cengage.com/coursepages/CU_Access_Spring
For a physical copy, the Third Edition (international) of this book is available at the UCSD Bookstore (see their website for details on free shipping) for approximately $20.
To brush up on proofs, use: Richard Hammack, Book of Proof, 2nd ed. (available for download here)
Machine visualization resources
There are multiple tools to help you visualize and test finite state machines, the foundational computer models we are studying in this class.
We will support two of these tools in CSE 105 this quarter: JFLAP and flap.js. JFLAP was developed starting in the 1990 by a team led by Susan Rodger (RPI, then Duke). It is now a mature tool with a lot of functionality. Some of the conventions and notation it uses differ from the course textbook for CSE 105.
The second tool, flap.js, is a webapp under development by a group of UCSD students that is being piloted in CSE 105. It is being customized for use in this class. Let me know
if you're interested in joining the development team for flap.js to help future CSE 105 students.
flap.js
The homepage for the tool is at
https://flapjs.github.io/FLAPJS-WebApp/; a
detailed tutorial is available here.
It currently has many features for designing and working with DFA and NFA. The module on PDA allows you to draw state diagrams.
JFLAP
The homepage for the tool is at
www.jflap.org; the current stable version is version 7.1.
Basic installation and configuration
For those who already have Java Virtual Machine installed. NOTE: you should be able to install JFLAP on systems with JVM even if you don't have install/Administrator rights.
- Download the JFLAP.jar file from Duke University.
- Double-click it to run JFLAP. If it doesn't launch, that probably means you don't have JVM installed. See instructions below.
- Go to Preferences, then select "Set the Empty String Character," and change it from "Lambda" to "Epsilon." This will make JFLAP match the notation we use in the book and in class for the empty string character.
If you don't already have JVM (Java Virtual Machine) installed on your computer
You'll need to get the JVM in order to run JFLAP. You will need install/Administrator rights to do this. To install:
- Go here for the latest version of Java.
- Download JDK 8 for your personal machine.
- After downloading, run the file (double-click) to install.
- After the install is finished, you may need to reboot.
- Now follow the "Basic Install and Configuration" instructions above to install and configure JFLAP.
Frequently asked questions about JFLAP
Regular Expressions Do not use whitespace in your regular expressions unless a space is a valid symbol in the alphabet. JFLAP uses a + symbol instead of the U used in the textbook
to indicate union.
Start and Accept States Don't forget to specify these when drawing your automata!
Multiple Transitions If you need multiple possible inputs for the same arrow in your diagram (e.g. if you can move between states on either a 0 or a 1), this is done by creating separate edges in JFLAP for each input symbol. JFLAP will combine these into one arrow on your diagram. Automata with transitions labeled with a comma (e.g. "0,1") are not equivalent, because those transitions will not be followed unless "0,1" actually appears in your input string.
Empty String In class and in the text, we use ε (epsilon) to denote the empty string. The instructions above help you change the JFLAP default λ (lambda) to match our conventions. If you need a state transition (or a stack symbol for PDA's) for ε, do not enter any characters into the text box for that transition and ε will appear. Entering a space does not work; that transition will be followed only if the input string has a space on it. Similarly, entering E or "epsilon" will not work because JFLAP will try to match those exact symbols in your input string for the transition.
Push Down Automata Each transition has three labels: an input symbol, a stack symbol to pop, and a stack symbol to push. JFLAP uses the semicolon (;) instead of a right arrow to separate the stack symbols. Any of the three labels can be the empty string. Settings: Your PDAs should be "Single Character Input" (this option appears when you first create an automaton), and they should accept by final state, not by empty stack.
Context Free Grammars If you have a production rule of the form "S -> A | B", enter it as two rules "S -> A" and "S -> B".
Typesetting (LaTeX) Resources
All submitted homework for this class must be typed. Diagrams may be hand-drawn and scanned and included in the typed document. You can use a word processing editor
if you like (Microsoft Word, Open Office, Notepad, Vim, Google Docs, etc.) but you might find
it useful to take this opportunity to learn LaTeX. LaTeX is a markup language used widely in computer science and mathematics. The homework assignments are typed using LaTeX and you can use the source files as templates for typesetting your solutions.
If you have never used LaTeX, we recommend cloud resources (e.g. Overleaf) that don't require you to download and install LaTeX on your local machine. In particular, Overleaf has great collaboration functionality if you choose to work with a group.
An open source LaTeX reference is here, and you can Google for many templates and examples to get you started.