Note the corrections and clarifications for Project 2,
incorporated in the specs document
(Thanks to Mr. Paolo Tioseco for bringing up these questions).
Project 2 specs have been posted.
September 5 seatwork: Convert the following grammar
to Chomsky Normal Form: G = ({S,T,N,A,V,O},{p,t,a,n,v}, P, S) where P is
S -> TNVOp
T -> t
T -> epsilon
N -> An
A -> aA
A -> epsilon
V -> aV
V -> v
O -> N
O -> epsilon
Midterm exam: August 13 (Part I: DFAs and Reg Ex) and 15
(Part II: Pumping Lemma and Grammars), during class period.
Reminder: your first project is due on July 30, midnight.
Submit through moodle
(enroll in the CS1302007 class).
Midterm exam will be during the week of August 16.
Time and venue will be finalized later.
July 18: Carry out the following seat work .
There is no need to submit this, but be prepared to
discuss the answers when your instructor arrives at 11am.
No classes on June 27. In the meantime, read section 2.3
on Nondeterministic Finite Automata
The textbook your instructor will use for this course is:
Introduction to Automata Theory, Languages, and Computation, 2nd ed
by Hopcroft, Motwani and Ullman, 2001.
The book is available in local bookstores; it is recommended that
you get a copy of the book.
Welcome to this website. Visit this site regularly
for course material and important announcements and updates.
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)
The Halting Problem
Note:
the last example discussed in class was flawed.
The Print-1-Problem (P1P):
should be stated as
"Given a program P and input i,
does P leave a 1 on the input tape?".
Try developing an unsolvability proof
for this problem.