Instructor:  Professor Anil Maheshwari
Office:  School of Computer Science, Carleton University, Ottawa, Canada K1S 5B6, Room 5364,  Herzberg Physics Building,
Phone: (613) 520-4333, Fax: (613) 520-4334,

OFFICE HOURS:  Tuesday 0915 to 1159. (On Sept. 13th/20th it is from 1030).
                  

E-mail: anil@scs.carleton.ca, WWW:http://www.scs.carleton.ca/~maheshwa.

• Introduction to the Theory of Computation, by Michael Sipser, PWS Publishing Company, Boston, 1997.
• Elements of the Theory of Computation (second edition), by Harry Lewis and Christos Papadimitriou, Prentice-Hall, 1998.
• Introduction to Languages and the Theory of Computation (third edition), by John Martin, McGraw-Hill, 2003.
• Introduction to Automata Theory, Languages, and Computation (second edition), by John Hopcroft, Rajeev Motwani, Jeffrey Ullman, Addison Wesley, 2001.

Last Date to Withdraw : November 7
Final Exam:  Please check which date and what time it is!
Final exam includes all the material covered in the class, corresponding sections in the notes, and all the material covered in the assignments and mid-term. This material includes numerous theorems, proofs, definitions, and exercises. Expect proving theorems, stating definitions, solving problems, in the Final Exam. I will mark the final exam in a fairly strict and straighforward manner and will not apply any exception to this. If you have concern on this, please let me know before the classes end.
A wrong proof is worth 0 marks.
A wrong definition is worth 0 marks.
A wrong use of a theorem is worth 0 marks.
A wrong formulation of a problem is worth 0 marks.
Missing states, or transitions, or rules, in a DFA, NFA, RE, CFG, PDAs and Turing Machines may cost huge deduction of marks.

Sept 26/28: More examples of NFA's, Definitions of NFA, acceptance and the language.
Equivalence of NFA and DFA.
Equivalence of NFA-DFA examples,  Closure of Regular Languages.
Closure of Regular Languages: union, concatenation, star, intersection, complement

Oct 4/6: Regular Expressions: From Regular Expressions to NFA
From DFA to Regular Expressions

OCt 11/13: From DFA to Regular Expressions and Pumping Lemma
Examples of Pumping Lemma.

Oct. 18/20 Introduction to Context Free Grammars.
Context Free Grammars.
Context Free Grammers, Context Free Languages and Examples.
Chomsky Normal Form.

Oct. 25 : Review, Problems from Assignment/Other Examples

Oct 27 MID-TERM

Nov 1/3: Push Down Automata's
PDA, NPDA and CFG-->NPDA
Pumping Lemma for CFG, Examples of non-context free languages.

Nov 8/10 Pumping Lemma for CFG.
         Turing machines +  Palindrome Example;
        
Nov. 15/17: Multi-tape Turing machines; equivalence with single-tape Turing machines. 
What is an algorithm. Church-Turing Thesis;

Novemner 22/24: Definitions of Turing-decidable;  
                Turing-recognizable languages. 
                Some decidable languages; Every Regular Language and context-free language is decidable;
There are languages that are not recognizable; The language A_TM is recognizable; The language A_TM is undecidable;
A language A is decidable if and only if A and its complement are both recognizable;
The complement of the language A_TM is not recognizable.  Halt is undecidable but recognizable.

Nov. 29/Dec. 1: P v/s NP and meaning of NP-completeness, Review + Problems + Course Evaluation.

HERE ARE SOME SAMPLE SOLUTIONS

SEE YOU IN EXAM

I do not read e-mails sent from yahoo - and other such domains. They goto my Trash folders. Please send e-mails from Carleton.Ca accounts only and I promise you that I will respond! 

• Assignment 4 is marked and can be picked from my office.
• Please collect all your assignments etc. from my office by December 15th  (After that they may disappear!)
  
• Mid-Terms were handed out on Thursday Nov. 3
• Assignment 2 was handed out on Tuesday Nov. 2.
  
• Mid-Term is in Steacie 310 on Thursday Oct. 27th from 1430 till 1600.
  
• Assignment 1 is posted at 10AM on Sept. 22. Its on this web-page.
  
• All assignments and  Mid-term are compulsory. Missed/late assignments and mid-term exams are worth 0%. 
• In case a student misses the mid-term due to medical reasons (doctor's note required),  then her/his marks will be added to the final exam. 
• In order to pass the course, you need to pass in each of the components, (a) Sum total of 4 Assignments, (b) Mid-term and (c) Finals, individually. 
• All marked assignments and Mid-term should be retained by students as proof of completion. Sometimes assignments are marked and handed back but the mark fails to get recorded.
  
• Students are encouraged to collaborate on assignments, but at the level of discussion only. When writing down the solutions, they must do so in their own words.
• Past experience has shown that those who do not put adequate effort into the assignments do not learn the material and have extremely high chances of failing the exams.
• Copying of assignments is not tolerated. Such cases will be referred to the Director of School of Computer Science and the Dean of Science for proper action.  THIS POLICY IS STRICTLY ENFORCED.
• The assignments will be normally marked in one weeks time and they will brought to the class for pickup. After that they will be available  from the (unattended) bin placed outside my office door.
  
• This explains why I am a bad teacher !
  

Accommodation of special needs students: Students with disabilities requiring academic accommodations in this course are encouraged to contact a coordinator at the Paul Menton Centre for Students with Disabilities to complete the necessary letters of accommodation. After registering with the PMC, make an appointment to meet and discuss your needs with me at least two weeks prior to the midterm exam. This is necessary in order to ensure sufficient time to make the necessary arrangements. Please check the
deadline for submitting completed forms to the Paul Menton Centre for formally scheduled exam accommodations with the Paul Menton Centre.