CS2200 - Languages, Machines and Computations

Meetings  

• Theme 1 : Finite Automata and Regular Languages - 12 meetings

  • Meeting 01 : Mon, Jan 12, 11:00 am-11:50 am

  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

  • Meeting 02 : Tue, Jan 13, 10:00 pm-10:50 pm

  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.

  • Meeting 03 : Wed, Jan 14, 09:00 am-09:50 am

  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].

  • Meeting 04 : Mon, Jan 19, 11:00 am-11:50 am

  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

  • Meeting 05 : Tue, Jan 20, 10:00 am-10:50 pm

  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.

  • Meeting 06 : Wed, Jan 21, 09:00 am-09:50 am

  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

  • Meeting 07 : Thu, Jan 22, 01:00 pm-01:50 pm

  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.

  • Meeting 08 : Tue, Jan 27, 10:00 pm-10:50 pm

  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.

  • Meeting 09 : Wed, Jan 28, 09:00 am-09:50 am

  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.

  • Meeting 10 : Thu, Jan 29, 01:00 pm-01:50 pm

  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.

  • Meeting 11 : Mon, Feb 02, 11:00 am-11:50 am

  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]

  • Meeting 12 : Tue, Feb 03, 10:00 pm-10:50 pm

  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

  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.

  • Meeting 14 : Thu, Feb 05, 12:00 pm-12:50 pm

  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

  • Meeting 15 : Mon, Feb 09, 11:00 am-11:50 am

  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

  • Meeting 16 : Tue, Feb 10, 10:00 pm-10:50 pm

  Non-determinisitic Finite Automaton (NFA). Examples.

  References	[Koz]
  Exercises
  Reading

  Non-determinisitic Finite Automaton (NFA). Examples.
  

  References:

  [Koz]

  • Meeting 17 : Wed, Feb 11, 09:00 am-09:50 am

  Notion of acceptance for an NFA. Computation tree. Examples.

  References	[Koz]
  Exercises
  Reading

  Notion of acceptance for an NFA. Computation tree. Examples.
  

  References:

  [Koz]

  • Meeting 18 : Mon, Feb 16, 11:00 am-11:50 am

  Converting an NFA to DFA - Subset construction.

  References	[Koz]
  Exercises
  Reading

  Converting an NFA to DFA - Subset construction.
  

  References:

  [Koz]

  • Meeting 19 : Tue, Feb 17, 10:00 am-10:50 am

  Regular Expressions. Definitions and Examples.

  References	[Koz]
  Exercises
  Reading

  Regular Expressions. Definitions and Examples.
  

  References:

  [Koz]

  • Meeting 20 : Wed, Feb 18, 09:00 am-09:50 am

  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].

  • Meeting 21 : Tue, Feb 24, 10:00 pm-10:50 pm

  Converting NFAs to regex. Homomorphisms.

  References
  Exercises
  Reading

  Converting NFAs to regex. Homomorphisms.
  

  References:

  None

  • Meeting 22 : Thu, Feb 26, 12:00 pm-12:50 pm

  To Be Announced

  References
  Exercises
  Reading

  To Be Announced
  

  References:

  None

• Theme 3 : Grammars and context-free languages - 15 meetings

  • Meeting 23 : Tue, Mar 03, 10:00 pm-10:50 pm

  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]

  • Meeting 24 : Wed, Mar 04, 09:00 am-09:50 am

  Formal definition of CFG. Examples: Balanced paranthesis with proof.

  References	[Koz]
  Exercises
  Reading

  Formal definition of CFG. Examples: Balanced paranthesis with proof.
  

  References:

  [Koz]

  • Meeting 25 : Thu, Mar 05, 12:00 pm-12:50 pm

  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]

  • Meeting 26 : Mon, Mar 09, 11:00 am-11:50 am

  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]

  • Meeting 27 : Tue, Mar 10, 10:00 pm-10:50 pm

  Conversion to Chomsky normal form. Greibach normal form.

  References	[Koz]
  Exercises
  Reading

  Conversion to Chomsky normal form. Greibach normal form.
  

  References:

  [Koz]

  • Meeting 28 : Wed, Mar 11, 09:00 am-09:50 am

  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]

  • Meeting 29 : Thu, Mar 12, 01:00 pm-01:50 pm

  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

  • Meeting 30 : Mon, Mar 16, 11:00 am-11:50 am

  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

  • Meeting 31 : Tue, Mar 17, 10:00 pm-10:50 pm

  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.

  • Meeting 32 : Mon, Mar 23, 11:00 am-11:50 am

  From CFGsto a PDA.

  References
  Exercises
  Reading

  From CFGsto a PDA.
  

  References:

  None

  • Meeting 33 : Tue, Mar 24, 10:00 pm-10:50 pm

  PDA to a CFG.

  References
  Exercises
  Reading

  PDA to a CFG.
  

  References:

  None

  • Meeting 34 : Wed, Mar 25, 09:00 am-09:50 am

  From PDA to a CFG.

  References
  Exercises
  Reading

  From PDA to a CFG.
  

  References:

  None

  • Meeting 35 : Thu, Mar 26, 12:00 pm-12:50 pm

  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

  • Meeting 36 : Wed, Apr 01, 12:00 pm-12:50 pm

  Applications to compilers: Parsing algorithms. CYK Parsing ALgorithm

  References	[Koz]
  Exercises
  Reading

  Applications to compilers: Parsing algorithms. CYK Parsing ALgorithm
  

  References:

  [Koz]

  • Meeting 37 : Mon, Apr 06, 11:00 am-11:50 am

  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

  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 etc
  

  References:

  [Koz]

  • Meeting 39 : Wed, Apr 08, 09:00 am-09:50 am

  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]

  • Meeting 40 : Thu, Apr 09, 12:00 pm-12:50 pm

  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]

  • Meeting 41 : Mon, Apr 13, 11:00 am-11:50 am

  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]

  • Meeting 42 : Wed, Apr 15, 09:00 am-09:50 am

  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

  • Meeting 43 : Thu, Apr 16, 12:00 pm-12:50 pm

  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]

  • Meeting 44 : Mon, Apr 20, 11:00 am-11:50 am

  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]

  • Meeting 45 : Thu, Apr 23, 12:00 pm-12:50 pm

  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

  • Meeting 46 : Mon, Apr 27, 11:00 am-11:50 am

  Post's theorem: statement. Review of topics covered.

  References
  Exercises
  Reading

  Post's theorem: statement. Review of topics covered.
  

  References:

  None

  • Meeting 47 : Wed, Apr 29, 09:00 am-09:50 am

  To Be Announced

  References
  Exercises
  Reading

  To Be Announced
  

  References:

  None

• Theme 5 : Tutorial Sessions - 10 meetings

  • Meeting 48 : Tue, Feb 10, 04:45 pm-05:35 pm

  Optional - 1

  References
  Exercises
  Reading

  Optional - 1
  

  References:

  None

  • Meeting 49 : Thu, Feb 19, 01:00 pm-01:50 pm

  Tutorial - 1

  References
  Exercises
  Reading

  Tutorial - 1
  

  References:

  None

  • Meeting 50 : Fri, Feb 20, 02:00 pm-03:00 pm

  Optional -2

  References
  Exercises
  Reading

  Optional -2
  

  References:

  None

  • Meeting 51 : Mon, Feb 23, 11:00 am-11:50 am

  Tutorial - 2

  References
  Exercises
  Reading

  Tutorial - 2
  

  References:

  None

  • Meeting 52 : Wed, Mar 18, 09:00 am-09:50 am

  Tutorial - 3

  References
  Exercises
  Reading

  Tutorial - 3
  

  References:

  None

  • Meeting 53 : Thu, Mar 19, 02:00 pm-03:00 pm

  Optional -3

  References
  Exercises
  Reading

  Optional -3
  

  References:

  None

  • Meeting 54 : Tue, Mar 24, 04:45 pm-05:35 pm

  Optional -4

  References
  Exercises
  Reading

  Optional -4
  

  References:

  None

  • Meeting 55 : Mon, Mar 30, 11:00 am-11:50 am

  Tutorial - 4

  References
  Exercises
  Reading

  Tutorial - 4
  

  References:

  None

  • Meeting 56 : Tue, Apr 21, 10:00 am-10:50 am

  Tutorial - 5

  References
  Exercises
  Reading

  Tutorial - 5
  

  References:

  None

  • Meeting 57 : Thu, Apr 23, 02:00 pm-03:00 pm

  Optional -5

  References
  Exercises
  Reading

  Optional -5
  

  References:

  None

• Theme 6 : Evaluation Meetings - 8 meetings

  • Meeting 58 : Thu, Feb 12, 01:00 pm-01:50 pm

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

  References
  Exercises
  Reading

  Short Exam - 1.
  Syllabus : Lectures 1-15.
  

  References:

  None

  • Meeting 59 : Wed, Feb 25, 08:00 am-08:50 am

  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

  • Meeting 60 : Thu, Mar 19, 01:00 pm-01:50 pm

  Short Exam - 2 <br> <B> Syllabus:</b> Lectures 16 - 31.

  References
  Exercises
  Reading

  Short Exam - 2
  Syllabus: Lectures 16 - 31.
  

  References:

  None

  • Meeting 61 : Tue, Mar 31, 08:00 am-08:50 pm

  Quiz - 2<br> <b>Syllabus:</b> Lectures 21- 35.

  References
  Exercises
  Reading

  Quiz - 2
  Syllabus: Lectures 21- 35.
  

  References:

  None

  • Meeting 62 : Wed, Apr 22, 09:00 am-09:50 am

  SE - 3 <br> <b> Syllabus </b >Lectures 32- 44.

  References
  Exercises
  Reading

  SE - 3
  Syllabus Lectures 32- 44.
  

  References:

  None

  • Meeting 63 : Tue, Apr 28, 04:50 pm-06:00 pm

  SE - 4 (optional)

  References
  Exercises
  Reading

  SE - 4 (optional)
  

  References:

  None

  • Meeting 64 : Tue, Apr 28, 10:00 pm-10:50 pm

  SE - 4 (Optional)

  References
  Exercises
  Reading

  SE - 4 (Optional)
  

  References:

  None

  • Meeting 65 : Thu, May 07, 09:00 am-12:00 pm

  End Sem Exam

  References
  Exercises
  Reading

  End Sem Exam
  

  References:

  None