The syllabus is here.
Hopcroft, Ullman and Motwani's Text Book
The following lecture notes are primarily developed by Dr. Phil Bernhard.
Occasionally I edit them.
Overview.
Induction.
Relations.
Countability.
Diagonalization.
Introduction to Formal Languages.
Finite Automata.
Regular Experssions.
Properties of Regular languages.
Context Free languages.
Pushdown Automata.
Pumping Lemma and other properties of CFL.
Non-context free language
Turing Machines.
Spring 2008:
A developing Tabular Plan for 2008.
In class Exercise 1 on proofs & functions(1/10/08)
HomeWork 1
HomeWork 2 on DFA
HomeWork 3 on NFA
HomeWork 4 on NFA-epsilon
HomeWork 5 on Regular Expression
In Class exercise 2/12/08 on Regular Expression
Exam 1 up to Regular Expression
HomeWork 6 on Context Free Grammar
HomeWork 7 on Push Down Automata
HomeWork 8 on Turing machine
Feed Back Sheet, mandatory, due 4/10/08 along with Hw7
Papers presentation assignments
Probabilistic Automata: Vidal et al., IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE,
VOL. 27, NO. 7, JULY 2005,
Probabilistic Finite-State Machines—Part I, and
Part-II
Grades, developing
------------------------------
Spring 2007:
Assignment 1 (due 1/17/07)
Assignment 2 (due 1/24/07)
Assignment 3 (due 2/7/07)
Assignment 4 (due 2/14/07)
Assignment 5 (due 2/28/07)
Assignment 6 (due 3/14/07)
Assignment 7 (due 3/28/07)
Assignment 8 (due 4/11/07)
Grades
Probabilistic Automata: Vidal et al., IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE,
VOL. 27, NO. 7, JULY 2005,
Probabilistic Finite-State Machines—Part I, and
Part-II
Presentation Schedule (due 4/11-25/07)
Programming project (due 5/2/07)
------------------------------
Spring 2006:
Assignment 1 (due 1/17/06)
Project (under construction!)
------------------------------
Spring 2005:
Assignment 1 (due 1/18/05)
Homework 2 (due 1/25/05)
Homework 3 (due 2/01/05 Tuesday)
Homework 4 (due 2/08/05 Tuesday)
Programming Assignment 1 (due 3/30/05 Wednesday)
Homework 5 (due 3/01/05 Tuesday)
Grades
Phew! I encourage you to drop by and take a look at your
final paper.
A pre-midterm quiz
Mid term on 3/22/05
Syllabus: up to CFG module.
Those who have made less than 30 in the test will get another chance to write
a test with same syllabus and similar questions, on 4/5/05 Tuesday before class.
Pick up the question at 6:15 pm from my office, find a place to sit in the Olin
Engg. Building, hand over your answers to me just before the class.
I will possibly make you sit in the GSA room.
Note that my next class starts at 6:30 pm. If you come late you may not
find me, that classroom keeps changing. Time of exam is same as before.
I will grade
these papers out of 30 points for the Midterm. Best of this test and the previous
Midterm will be picked as the grade for Midterm.
Homework 6
(due date extended to 4/07/05 Thursday)
Quiz on PDA and Turing Machine. (open book) 4/26/05 Tuesday
I WOULD LIKE TO HAVE SOME FEEDBACK ON THE COURSE. EACH OF YOU WILL SUBMIT
A PRINTED WRITEUP OF ONE PAGE ON HOW THE COURSE CAN BE IMPROVED, AND IF
THERE WAS ANY WEAKNESS THAT NEEDS TO BE FIXED. SEPARATE TWO ITEMS
(1) COURSE CONTENT, (2) COURSE DELIVERY. DO NOT WRITE YOUR NAME ON THE
PAGE. QUIZ ATTENDANCE WIL BE LINKED TO YOUR SUBMITTING THIS PAGE.
Final Exam: May 3, 05, Tuesday:8:30-10:30 pm
Syllabus: For regular questions: Regular expression onwards; There
may be a set of short questions, which could be from anywhere in the syllabus
(True/False, fill in the blank, etc.). Format: same as in the midterm, open
book, open slides...
------------------------------
Spring 2004:
Assignment 1 (due 1/26/04): Text Exercise 2.2.4 a,b,c
Assignment 2 (due 2/17/04): here.
The Problem 6.3.5.b solution.
The syllabus for the Mid Term: from recursive language through pushdown
automata. Suggestions: recursive language to NFA-epsilon, pumping
lemma and proving non-regularity of languages, context free grammar,
CFG to PDA conversion (Greibach normal form), and PDA.
Project
Grades so far
E-mail:
dmitra@zach.fit.edu