CS 130 Theory of Computation
2nd Semester, 2010-2011
John Paul Vergara, PhD

Announcements

• Test files for project 2 have been posted. Deadline moved to Sunday, Feb 20.
• Last class day on Feb 15; no classes on Feb 17.
• Project 2 specs have been finalized and posted.
• Happy new year! Sample output files have been posted. Since they were posted just now, I am extending the project deadline to January 10. Note minor correction on specs (ENDTAGHEAD should be included as a token).
• No classes on Tuesday, December 21. Have a good Christmas break. Work on your project (specs are posted below).
• Midterm exam on December 16, in class: Sample questions for review.
• Welcome to this website. Visit this site regularly for course material and important announcements and updates.

Projects

• Project 1 (due Friday, January 7 January 10: Specs
  Sample input files (note: your browser will render the tables, so you need to "view source"): tab1.html , tab2.html , manycases.txt (updated!)
  Sample output files: tab1out.txt , tab2out.txt , mcout.txt
  note: you need to recover after detecting an error; continue scanning either on or after the offending character).
• Project 2 (due Friday, February 18 Sunday, Feb 20): (Updated) Specs
  Clarifications:
  • You will need to add tokens for [ and ].
  • You may abort the program after encountering the first parsing error but you need to output an error message (through console output).
  • Just process the first table in the html file; ignore all tokens that precede the TAGIDENT token labeled table and all tokens that succeed the corresponding ENDTAGHEAD, IDENT(table), and GTHAN tokens.
  • Table entries that begin with = must be followed by a valid expression, and nothing else; table entries that begin with a [ must be followed by a valid expression, then ], then nothing else
  Test cases courtesy of your grader, Wil Li; error cases are those with the word error in the file names.

Homework

• HW 1 (due Wednesday, Nov 24):
  Revise one of the calculator programs posted below such that it supports more complex computations.
  Currently, it accepts 2-operand strings like 123+456= or 25-4=. Arrange its so that multiply and divide (assume integer division) operators and multiple operands are supported;
  i.e., strings like 12+34-56= and 5+33-6/8+1*2= should be acceptable. Assume left-to-right precedence, not MDAS (5+33-6/8+1*2= 10). Display partial results as each succeding operator is pressed. Submit the revised Java program via moodle.
• HW 2 (due Tuesday, Dec 7):
  
  1. Provide a formal definition for a Mealy Machine.
  2. Construct a Mealy Machine for "division by 4": given a string of digits representing a number n, output n/4. Provide a diagram and list and describe each component explained in item 1.
  Place your answers in an MS-Word document and submit through moodle.

Course Material

• Course overview
• Intro to strings and languages
• Deterministic Finite Automata
  Java calculator program that demonstrates a DFA when processing button actions;
  this version uses a state transition array
• Alternative notation for state transitions
• Nondeterministic Finite Automata ( updated! )
• Regular Expressions ( updated! )
  Java Program that demonstrates DFA to Regular expression conversion; The DFA used is the one that recognizes strings from the alphabet {0,1,2} that are divisible by 3.
• The Pumping Lemma
• Grammars
• Push-down Automata
• About Grammars
• Java program that demonstrates Recursive Descent Parsing,
  Wiki site that demonstrates recursive descent parsing in C.
  Another Java program that demonstrates Recursive Descent Parsing, this time with simple arithmetic expressions like 1+1*-1*(-1+1)
• Turing Machines
• The Halting Problem
• Undecidable Problems
• P and NP
  Millenium Prize Problems (includes P vs NP question)

Links

• Moodle