FOUNDATIONS OF COMPUTING SCIENCE Autumn 201718 

Teaching Assistants: Antonio Bruto da Costa, Sudipa Mandal, Madhumita Mallick 

Introduction  Prof. Pallab Dasgupta  


Quiz 1  Regular Languages  


Regular Languages  Prof. Pallab Dasgupta  
Preliminaries, DFAs, NFAs, Understanding NonDeterminism  

Regular Languages  Prof. Pallab Dasgupta  
Closure Properties (Union, Intersection, Concatenation), Introduction to Regular Expressions and the Pumping Lemma [Student Task: What is the pumping length? And what is its impact in relation to Regular Languages?] 

Tutorial 1  Regular Languages  


Context Free Languages  Prof. Pallab Dasgupta  
Context Free Languages, Context Free Grammars, Ambiguity 

Context Free Languages Contd.  Prof. Pallab Dasgupta  
CFL Ambiguity Contd., Chomsky Normal Form, Push Down Automata, Excercise: CFGs <=> PDAs interconversion 

Quiz 2  Context Free Languages  



Context Free Languages Contd.  Prof. Pallab Dasgupta  
Pumping Lemma for Context Free Languages (Date for Class Test 1 TBD) 

Context Free Languages Contd.  Prof. Pallab Dasgupta  
Pumping Lemma for Context Free Languages and Closure Properties for CFLS, NPDAs are strictly more powerful than DPDAs 

NonRegular Languages  
Some nonregular languages also satisfy the Pumping Lemma for Regular Languages. Read the attached document  

The ChurchTuring Thesis  
An introduction to Turing Machines and configurations of the machine  

The ChurchTuring Thesis  
Reducability and Decidability; Variants of the Turing Machines  

Tutorial : Context Free Languages  
Worked on CNF, Pumping Lemmma, English Descriptions of CCFGs. Students must attempt unsolved problems.  

The ChurchTuring Thesis  
Decidability and Recognizability of Languages  

The ChurchTuring Thesis  
Decidability and the Halting Problems  

Tutorial : Turing Machines  
Worked on CNF, Pumping Lemmma, English Descriptions of CCFGs. Students must attempt unsolved problems.  

Class Test 1 (24082017)  [Solutions] 
Class Test 1  

Reducability Decidability  [PDFDecidability] 
Reducability Decidability  

Complexity Theory  [Space Complexity Slides] 
[Polynomial Hierarchy  Additional Material]  

Tutorial: Complexity Theory  


Logic and Reasoning  


Tutorial: Propositional Logic  


Tutorial: Predicate Logic  


Class Test 2  


Past Question Papers  