CSE 105 Fall 2022: Automata and Computability Theory

Instructor: Daniele Micciancio
TAs: Parth Doshi, Satvik Gupta, Saketh Khandavalli, Venkat Krishnamohan, Shreya Saha, Madhav Wagle, Satish Yerva

Syllabus and Policies: Read the course Syllabus for course description, textbook, prerequisites and objectives, detailed information about assignments, exams, grading, and other course policies. Pay special attention to academic honesty and collaboration policies.

Canvas: https://canvas.ucsd.edu/courses/40756. If you are enrolled in this class, you should have access to it through Canvas. We will use Canvas to distribute homework assignments, solutions, lecture notes (slides), and any additional course material. Enrollment in Piazza and Gradescope is automatically handled by Canvas.

Discussion board: Piazza. This will be the main platform to ask/answer questions and post course announcements. Enrollment/access to piazza is handled automatically by Canvas, and does not allow manual additions. Please check that you can access the discussion board, and enable email notifications. If you just added the class, you may have to wait for the roster to sync before you have access.

Homework submission and Grades: We will use Gradescope for homework submission and grading. Each homework should be done in groups of one to three people, see syllabus for details. Enrollment/access to gradescope is handled automatically by Canvas. If you just added the class, you may have to wait for the roster to sync before you have access.

Other tools: See below for active learning/attendance (iClickers), machine visualization (JFLAP/flap.js) and homework typesetting (LaTeX/Overleaf)

Contact Information: For general/technical questions that may be of interest to other students, please use the Piazza discussion board. If you are not sure if your question should be publicly posted, or want only the instructors/TAs to read it, you can still use piazza and mark it as private. For in-person questions/help about homework assignments, you should attend discussion and office hours of any of the course staff. Office hours and other events will be posted on the canvas calendar.

Course Calendar and Reading Schedule

Lectures: MW 5:00p-6:20p (PETER 108)
Podcast recordings of the lectures will be available (shortly after class, typically within a day) at https://podcast.ucsd.edu/watch/fa22/cse105_a00 for review, or for making up for occasionally missing a lecture.

Discussions: F 12:00p-12:50p (WLH 2001)
An alternate (online) discussion session is being scheduled, also on Friday, tentatively at 1:30p-2:20p. (See canvas calendar to confirm the time and get the zoom link.) The two discussions cover the same material, and you should attend only one.

Important dates:

Here is a weekly schedule of topics covered in class, exams and homework due dates. Reading assignments are tentative, and they are provided in case you want to read ahead. Chapter pointers refer to the course textbook, M. Sipser, Introduction to the Theory of Computation.

Date Topic Reading Notes
Week 1 DFA + closure Ch. 0 + 1.1 HW1 due (Sun Oct 2) + clicker registration deadline
Week 2 NFAs, RegEx Ch. 1.2 + 1.3 HW2 due (Fri Oct 7)
Week 3 Pumping Lemma Ch. 1.4 HW3 due (Fri Oct 14)
Week 4 CFGs Ch. 2.1 Midterm 1 (Wed Oct 19)
Week 5 PDAs, TM Ch. 2 + 3.1 HW4 due (Fri Oct 28)
Week 6 TM variants and Decidability Ch. 3 + 4.1 HW5 due (Fri Nov 4)
Week 7 Diagonalization Ch. 4.2 Midterm 2 (Wed Nov 9), Veterans’ day holiday (Fri Nov 11)
Week 8 Undecidabiltiy and Reductions Ch 5 HW6 due (Fri Nov 18)
Week 9 More Reductions Ch 5 Thanksgiving holiday (Thu Nov 25)
Week 10 Time complexity Ch 7 HW7 due (Wed Nov 30)
Final week Final exam (Thu Dec 8)

iClickers

You should have your clicker registered with Canvas by Sun October 2. (See course syllabus for clicker and attendance policy.) How to register your clicker in Canvas:

  1. Login to Canvas
  2. Open iClicker Tool: Navigate to the iClicker tab (1) in your course’s left navigation bar. Enter your iClicker’s remote ID (2) located on the back of your remote, and click Register (3).
  3. Confirm Registration: Make sure your registration number is correct. If it is not, click Remove to start over.

Machine visualization (JFLAP / flap.js)

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 are 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 https://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.

  1. Download the JFLAP.jar file from Duke University.
  2. Double-click it to run JFLAP. If it doesn’t launch, that probably means you don’t have JVM installed. See instructions below.
  3. 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:

  1. Go here for the latest version of Java.
  2. Download JDK 8 for your personal machine.
  3. After downloading, run the file (double-click) to install.
  4. After the install is finished, you may need to reboot.
  5. Now follow the “Basic Install and Configuration” instructions above to install and configure JFLAP.

Answers to 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”.

Homework Typesetting (LaTeX / Overleaf)

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 the LaTex document preparation system. 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.