CS 130 Theory of Computation
2nd Semester, 2010-2011
John Paul Vergara, PhD
DISCS Policies on Academic Integrity and Lab Use
- 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.
- Project 1 (due
Friday, January 7 January 10:
Sample input files (note: your browser will render the tables,
so you need to "view source"):
Sample output files:
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):
Test cases courtesy of your grader, Wil Li;
error cases are those with the word error in the file names.
- 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
- 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
i.e., strings like 12+34-56= and 5+33-6/8+1*2= should be acceptable.
Assume left-to-right precedence, not MDAS
Display partial results as each succeding operator is pressed.
Submit the revised Java program via moodle.
- HW 2 (due Tuesday, Dec 7):
Place your answers in an MS-Word document and submit through
- Provide a formal definition for a Mealy Machine.
- Construct a Mealy Machine for "division by 4":
given a string of digits representing a number n,
Provide a diagram and list and describe each component
explained in item 1.