Meetings

Click on the theme item for the meeting plan for that theme.Click on the meeting item for references, exercises, and additional reading related to it.

**Theme 1 : Finite Automata and Regular Languages**- 12 meetings- Meeting 01 : Mon, Jan 12, 11:00 am-11:50 am
- Meeting 02 : Tue, Jan 13, 10:00 pm-10:50 pm
- Meeting 03 : Wed, Jan 14, 09:00 am-09:50 am
- Meeting 04 : Mon, Jan 19, 11:00 am-11:50 am
- Meeting 05 : Tue, Jan 20, 10:00 am-10:50 pm
- Meeting 06 : Wed, Jan 21, 09:00 am-09:50 am
- Meeting 07 : Thu, Jan 22, 01:00 pm-01:50 pm
- Meeting 08 : Tue, Jan 27, 10:00 pm-10:50 pm
- Meeting 09 : Wed, Jan 28, 09:00 am-09:50 am
- Meeting 10 : Thu, Jan 29, 01:00 pm-01:50 pm
- Meeting 11 : Mon, Feb 02, 11:00 am-11:50 am
- Meeting 12 : Tue, Feb 03, 10:00 pm-10:50 pm

Administrative announcements. Outline of the course. Introduction, perspectives on computation. References Exercises Reading Administrative announcements. Outline of the course. Introduction, perspectives on computation.References: None Elementary notions of computation. Example notions of computation: Compass and ruler constructions of the Greeks. Formal definition of a finite automata.<br> Introduction of TAs and TA groupings. References <a href="http://en.wikipedia.org/wiki/Compass-and-straightedge_construction"> Compass and Straightedge constructions</a>. Exercises Reading See <a href="http://www.math.uiuc.edu/~rotman/ruler.pdf"> Ruler and Compass contructions </a> a rigorous and expository article by Rotman. Elementary notions of computation. Example notions of computation: Compass and ruler constructions of the Greeks. Formal definition of a finite automata.

Introduction of TAs and TA groupings.References: Compass and Straightedge constructions. Reading: See Ruler and Compass contructions a rigorous and expository article by Rotman. Formal definition of an automaton: Deterministic finite automata (DFA). Examples. State diagrams and configurations. Notion of a language. Languages accepted by DFAs: Regular Languages. References Lecture 3 of [Koz]. Exercises Reading Formal definition of an automaton: Deterministic finite automata (DFA). Examples. State diagrams and configurations. Notion of a language. Languages accepted by DFAs: Regular Languages.References: Lecture 3 of [Koz]. More examples of regular languages. Word problem on finite groups as a regular language. References [Koz] Book Exercises Reading More examples of regular languages. Word problem on finite groups as a regular language.References: [Koz] Book Proving correctness of the DFA: by induction on the length of the string. Set theoretic properties of regular languages: Complementation. References [Koz] book. Exercises Reading Proving correctness of the DFA: by induction on the length of the string. Set theoretic properties of regular languages: Complementation.References: [Koz] book. Proerties of regular langauges: Union, Intersection, Complement. Showing that a language is not regular. References [Koz] Book Exercises Reading Proerties of regular langauges: Union, Intersection, Complement. Showing that a language is not regular.References: [Koz] Book The pumping lemma: formal statement and proof. PRIMES is not regular. Game against the demon. References [Koz] Book. Exercises Reading The pumping lemma: formal statement and proof. PRIMES is not regular. Game against the demon.References: [Koz] Book. More applications of the pumping lemma. Towards a structural characterization of regular languages. Myhill-Nerode relations. References [Koz] Book. Exercises Reading More applications of the pumping lemma. Towards a structural characterization of regular languages. Myhill-Nerode relations.References: [Koz] Book. Myhill-Nerode relations to DFA and vice versa. Myhill Nerode theorem. References [Koz] Book. Exercises Reading Myhill-Nerode relations to DFA and vice versa. Myhill Nerode theorem.References: [Koz] Book. Myhil Nerode theorem: A canonical relation on languages that is coarsest among all Myhil-Nerode relations. References [Koz] Book. Exercises Reading Myhil Nerode theorem: A canonical relation on languages that is coarsest among all Myhil-Nerode relations.References: [Koz] Book. Proof of coarseness property. Applications of Myhill-Nerode theorem for proving non-regularity of languages. Coarseness of M-N relations==> DFA with a minimum number of states. DFA minimization problem. References [Koz] Exercises Reading Proof of coarseness property. Applications of Myhill-Nerode theorem for proving non-regularity of languages. Coarseness of M-N relations==> DFA with a minimum number of states. DFA minimization problem.References: [Koz] DFA Minimization problem. Quotient Automata consrunction. An algorithm for DFA minimization. References Exercises Reading DFA Minimization problem. Quotient Automata consrunction. An algorithm for DFA minimization.References: None **Theme 2 : Non-determinism and two-way access**- 10 meetings- Meeting 13 : Wed, Feb 04, 09:00 am-09:50 am
- Meeting 14 : Thu, Feb 05, 12:00 pm-12:50 pm
- Meeting 15 : Mon, Feb 09, 11:00 am-11:50 am
- Meeting 16 : Tue, Feb 10, 10:00 pm-10:50 pm
- Meeting 17 : Wed, Feb 11, 09:00 am-09:50 am
- Meeting 18 : Mon, Feb 16, 11:00 am-11:50 am
- Meeting 19 : Tue, Feb 17, 10:00 am-10:50 am
- Meeting 20 : Wed, Feb 18, 09:00 am-09:50 am
- Meeting 21 : Tue, Feb 24, 10:00 pm-10:50 pm
- Meeting 22 : Thu, Feb 26, 12:00 pm-12:50 pm

A minimization algorithm for DFAs. DFAs with two-way access. Formal definition. References [Koz] CHapter 17. Exercises Reading A minimization algorithm for DFAs. DFAs with two-way access. Formal definition.References: [Koz] CHapter 17. Formal Definition of 2-way DFAs (2DFA). Languages accepted by 2DFAs are regular. Proof using Myhill Nerode theorem. References Exercises Reading Formal Definition of 2-way DFAs (2DFA). Languages accepted by 2DFAs are regular. Proof using Myhill Nerode theorem.References: None Languages accepted by 2DFAs are regular. Proof using Myhill Nerode theorem. Introduction to non-determinism. References Exercises Reading Languages accepted by 2DFAs are regular. Proof using Myhill Nerode theorem. Introduction to non-determinism.References: None Non-determinisitic Finite Automaton (NFA). Examples. References [Koz] Exercises Reading Non-determinisitic Finite Automaton (NFA). Examples.References: [Koz] Notion of acceptance for an NFA. Computation tree. Examples. References [Koz] Exercises Reading Notion of acceptance for an NFA. Computation tree. Examples.References: [Koz] Converting an NFA to DFA - Subset construction. References [Koz] Exercises Reading Converting an NFA to DFA - Subset construction.References: [Koz] Regular Expressions. Definitions and Examples. References [Koz] Exercises Reading Regular Expressions. Definitions and Examples.References: [Koz] Regular expressions produce regular languages. Converting regex to NFAs. Converting NFAs to regex. References [Koz]. For converting DFA/NFA to regex please see Proof of Theorem 2.3.2 in [LP] (Second edition of the book). The proof in the class was from [LP]. Exercises Reading Regular expressions produce regular languages. Converting regex to NFAs. Converting NFAs to regex.References: [Koz]. For converting DFA/NFA to regex please see Proof of Theorem 2.3.2 in [LP] (Second edition of the book). The proof in the class was from [LP]. Converting NFAs to regex. Homomorphisms. References Exercises Reading Converting NFAs to regex. Homomorphisms.References: None To Be Announced References Exercises Reading To Be AnnouncedReferences: None **Theme 3 : Grammars and context-free languages**- 15 meetings- Meeting 23 : Tue, Mar 03, 10:00 pm-10:50 pm
- Meeting 24 : Wed, Mar 04, 09:00 am-09:50 am
- Meeting 25 : Thu, Mar 05, 12:00 pm-12:50 pm
- Meeting 26 : Mon, Mar 09, 11:00 am-11:50 am
- Meeting 27 : Tue, Mar 10, 10:00 pm-10:50 pm
- Meeting 28 : Wed, Mar 11, 09:00 am-09:50 am
- Meeting 29 : Thu, Mar 12, 01:00 pm-01:50 pm
- Meeting 30 : Mon, Mar 16, 11:00 am-11:50 am
- Meeting 31 : Tue, Mar 17, 10:00 pm-10:50 pm
- Meeting 32 : Mon, Mar 23, 11:00 am-11:50 am
- Meeting 33 : Tue, Mar 24, 10:00 pm-10:50 pm
- Meeting 34 : Wed, Mar 25, 09:00 am-09:50 am
- Meeting 35 : Thu, Mar 26, 12:00 pm-12:50 pm
- Meeting 36 : Wed, Apr 01, 12:00 pm-12:50 pm
- Meeting 37 : Mon, Apr 06, 11:00 am-11:50 am

Are the set of regular expressions themselves regular? Introduction to Context free grammars. Motivation and Example of a simplified C language. References [Koz] Exercises Reading Are the set of regular expressions themselves regular? Introduction to Context free grammars. Motivation and Example of a simplified C language.References: [Koz] Formal definition of CFG. Examples: Balanced paranthesis with proof. References [Koz] Exercises Reading Formal definition of CFG. Examples: Balanced paranthesis with proof.References: [Koz] Another example of a CFG: Balanced Parenthesis with full proof. Parse trees. References [Koz] Exercises Reading Another example of a CFG: Balanced Parenthesis with full proof. Parse trees.References: [Koz] Parse trees. Ambiguity in CFGs: an example. Normal forms: Chomsky Normal Form and Greibach normal form. Converting CFGs into normal forms. References [Koz] Exercises Reading Parse trees. Ambiguity in CFGs: an example. Normal forms: Chomsky Normal Form and Greibach normal form. Converting CFGs into normal forms.References: [Koz] Conversion to Chomsky normal form. Greibach normal form. References [Koz] Exercises Reading Conversion to Chomsky normal form. Greibach normal form.References: [Koz] Pumping Lemma for CFLs. Applications. Closure properties of CFLs: Union, Concatenation, Kleene closure. References [Koz] Exercises Reading Pumping Lemma for CFLs. Applications. Closure properties of CFLs: Union, Concatenation, Kleene closure.References: [Koz] More closure properties of CFLs: <b> not closed</b> under intersection and complementation. Intersection with regular languages. References Exercises Reading More closure properties of CFLs:**not closed**under intersection and complementation. Intersection with regular languages.References: None Towards a machine model for Context free languages: Push down automata - an NFA with push/pop stack. Formal definition. Notion of acceptance. Examples. References Exercises Reading Towards a machine model for Context free languages: Push down automata - an NFA with push/pop stack. Formal definition. Notion of acceptance. Examples.References: None Properties of pushdown automaton. Acceptance by final state vs empty stack (without proof). Languages accepted by PDAs. References [Koz]. For final state vs empty stack see Supplementary Lecure E in [Koz]. A complete formal construction can be found there. Exercises Reading Properties of pushdown automaton. Acceptance by final state vs empty stack (without proof). Languages accepted by PDAs.References: [Koz]. For final state vs empty stack see Supplementary Lecure E in [Koz]. A complete formal construction can be found there. From CFGsto a PDA. References Exercises Reading From CFGsto a PDA.References: None PDA to a CFG. References Exercises Reading PDA to a CFG.References: None From PDA to a CFG. References Exercises Reading From PDA to a CFG.References: None From PDAs to CFG: converting PDA to a single state PDA, concluding arguments. Applications to compilers: Parsing algorithms. References Exercises Reading From PDAs to CFG: converting PDA to a single state PDA, concluding arguments. Applications to compilers: Parsing algorithms.References: None Applications to compilers: Parsing algorithms. CYK Parsing ALgorithm References [Koz] Exercises Reading Applications to compilers: Parsing algorithms. CYK Parsing ALgorithmReferences: [Koz] Restrictions of Context Free languages. Notion of effective computability. References Exercises Reading Restrictions of Context Free languages. Notion of effective computability.References: None **Theme 4 : Turing machines and Computability**- 10 meetings- Meeting 38 : Tue, Apr 07, 10:00 pm-10:50 pm
- Meeting 39 : Wed, Apr 08, 09:00 am-09:50 am
- Meeting 40 : Thu, Apr 09, 12:00 pm-12:50 pm
- Meeting 41 : Mon, Apr 13, 11:00 am-11:50 am
- Meeting 42 : Wed, Apr 15, 09:00 am-09:50 am
- Meeting 43 : Thu, Apr 16, 12:00 pm-12:50 pm
- Meeting 44 : Mon, Apr 20, 11:00 am-11:50 am
- Meeting 45 : Thu, Apr 23, 12:00 pm-12:50 pm
- Meeting 46 : Mon, Apr 27, 11:00 am-11:50 am
- Meeting 47 : Wed, Apr 29, 09:00 am-09:50 am

Restrictions of Context Free languages. Notion of effective computability. Various notions of effective computability: mu-recursive functions, lambda calculus, Turing machines etc References [Koz] Exercises Reading Restrictions of Context Free languages. Notion of effective computability. Various notions of effective computability: mu-recursive functions, lambda calculus, Turing machines etcReferences: [Koz] Introduction to Turing Machines. Formal defintion. Church Turing thesis. Examples. Recusrive and recursively enumerable languages. References [Koz] Exercises Reading Introduction to Turing Machines. Formal defintion. Church Turing thesis. Examples. Recusrive and recursively enumerable languages.References: [Koz] More examples. Equivalent Models: multitape Turing machines, Two stack machines, Counter automata. References [Koz] Exercises Reading More examples. Equivalent Models: multitape Turing machines, Two stack machines, Counter automata.References: [Koz] Encoding of Turing Machines. Universal Turing machine. MP: member ship problem, HP: Halting problem. HP, and MP are r.e. References [Koz] Exercises Reading Encoding of Turing Machines. Universal Turing machine. MP: member ship problem, HP: Halting problem. HP, and MP are r.e.References: [Koz] Can there be a total TM for HP? NO. Proof using cantor's diagonalization. References Exercises Reading Can there be a total TM for HP? NO. Proof using cantor's diagonalization.References: None More non-recursive languages. Notion of reductions. Usefulness of reductions. References [Koz] Exercises Reading More non-recursive languages. Notion of reductions. Usefulness of reductions.References: [Koz] Examples of reductions. Problems on Turing machines. HP_null is not recursive. References [Koz] Exercises Reading Examples of reductions. Problems on Turing machines. HP_null is not recursive.References: [Koz] Closure properties of REC and RE. If a language and its complement are RE the it must be REC. <br> TCF forms. References Exercises Reading Closure properties of REC and RE. If a language and its complement are RE the it must be REC.

TCF forms.References: None Post's theorem: statement. Review of topics covered. References Exercises Reading Post's theorem: statement. Review of topics covered.References: None To Be Announced References Exercises Reading To Be AnnouncedReferences: None **Theme 5 : Tutorial Sessions**- 10 meetings- Meeting 48 : Tue, Feb 10, 04:45 pm-05:35 pm
- Meeting 49 : Thu, Feb 19, 01:00 pm-01:50 pm
- Meeting 50 : Fri, Feb 20, 02:00 pm-03:00 pm
- Meeting 51 : Mon, Feb 23, 11:00 am-11:50 am
- Meeting 52 : Wed, Mar 18, 09:00 am-09:50 am
- Meeting 53 : Thu, Mar 19, 02:00 pm-03:00 pm
- Meeting 54 : Tue, Mar 24, 04:45 pm-05:35 pm
- Meeting 55 : Mon, Mar 30, 11:00 am-11:50 am
- Meeting 56 : Tue, Apr 21, 10:00 am-10:50 am
- Meeting 57 : Thu, Apr 23, 02:00 pm-03:00 pm

Optional - 1 References Exercises Reading Optional - 1References: None Tutorial - 1 References Exercises Reading Tutorial - 1References: None Optional -2 References Exercises Reading Optional -2References: None Tutorial - 2 References Exercises Reading Tutorial - 2References: None Tutorial - 3 References Exercises Reading Tutorial - 3References: None Optional -3 References Exercises Reading Optional -3References: None Optional -4 References Exercises Reading Optional -4References: None Tutorial - 4 References Exercises Reading Tutorial - 4References: None Tutorial - 5 References Exercises Reading Tutorial - 5References: None Optional -5 References Exercises Reading Optional -5References: None **Theme 6 : Evaluation Meetings**- 8 meetings- Meeting 58 : Thu, Feb 12, 01:00 pm-01:50 pm
- Meeting 59 : Wed, Feb 25, 08:00 am-08:50 am
- Meeting 60 : Thu, Mar 19, 01:00 pm-01:50 pm
- Meeting 61 : Tue, Mar 31, 08:00 am-08:50 pm
- Meeting 62 : Wed, Apr 22, 09:00 am-09:50 am
- Meeting 63 : Tue, Apr 28, 04:50 pm-06:00 pm
- Meeting 64 : Tue, Apr 28, 10:00 pm-10:50 pm
- Meeting 65 : Thu, May 07, 09:00 am-12:00 pm

Short Exam - 1. <br> <b> Syllabus </b>: Lectures 1-15. References Exercises Reading Short Exam - 1.

**Syllabus**: Lectures 1-15.References: None Quiz - 1<br> <b> Syllabus </b> Lectures 1-20.<br> <b> Venue </b> CS 24 & CS26. References Exercises Reading Quiz - 1

**Syllabus**Lectures 1-20.

**Venue**CS 24 & CS26.References: None Short Exam - 2 <br> <B> Syllabus:</b> Lectures 16 - 31. References Exercises Reading Short Exam - 2

**Syllabus:**Lectures 16 - 31.References: None Quiz - 2<br> <b>Syllabus:</b> Lectures 21- 35. References Exercises Reading Quiz - 2

**Syllabus:**Lectures 21- 35.References: None SE - 3 <br> <b> Syllabus </b >Lectures 32- 44. References Exercises Reading SE - 3

**Syllabus**Lectures 32- 44.References: None SE - 4 (optional) References Exercises Reading SE - 4 (optional)References: None SE - 4 (Optional) References Exercises Reading SE - 4 (Optional)References: None End Sem Exam References Exercises Reading End Sem ExamReferences: None