Sign In
 

 ICS 355: Theory Of Computing

​Course Information

Class/Laboratory Schedule: 

Three 50 minutes lectures, per week (3-0-3)

Designation:   Elective Course

Course Level:   Undergraduate

Prerequisites

Prerequisite(s) by Topic: 

  • DS1. Functions, Relations and Sets
  • DS3. Proof Techniques
  • DS4. Basics of Counting

Prerequisite Courses: 


Catalog Description:
 
Regular Grammars: equivalence of DFA, NDFA and regular expressions, pumping lemma,emptiness and membership. Context-Free Grammars: parsing and ambiguity, normal forms,applications, equivalence of PDA's and CFG's, pumping lemma, emptiness and membership.Turing Machine: programming techniques for Turing machines, equivalence of one-tape and multitape TM's, universal Turing-machine. Undecidability: recursively enumerable and recursive languages, undecidability, problem eduction, undecidable problems of CFG's, RE's and TM's.

Textbook(s): 

P. Linz, An Introduction to Formal Languages and Automata, 4th Edition, Jones and Bartlett Publishers, 2006.

Reference(s) and Other Material: 

  • J. Hopcroft, R.Motwani and J. Ullman, Introduction to Automata Theory, Languages, and Computation, Addison Wesley, 2001.
  • Lecture notes on Theory of Computing (handout)

Course Outcomes: 

  • Design and explain regular languages in different notations: DFA, NFA, regular
  • expressions and grammars, and convert between these notations.
  • Use the pumping lemma to prove that a given language is not regular.
  • Understand pushdown automata, context-free grammars, and their normal forms, and
  • apply CYK algorithm on context-free languages.
  • Understand the Chomsky hierarchy for language classification, and determine the class of
  • a given language and the type of a given grammar.
  • Understand the Turing thesis and its implications, and explain basic concepts of the
  • theory of decidability.

Topics Covered: 

  • Introduction to alphabet, languages, and regular expressions.
  • Regular Languages. Finite-state automata, DFA and NFA.
  • Equivalence of DFA, NFA and regular expression.
  • Pigeon-hole principle, pumping lemma, and non-regular languages.
  • Grammar, Context-Free and Context-Sensitive Grammar.
  • Context-Free Languages and Pushdown Automata.
  • Turing Machines. Recursive and Recursively enumerable languages. Linear
  • Bounded automata.
  • Hierarchy of Formal Languages and the Chomsky Hierarchy.
  • Undecidability, the Halting Problem, Hilbert 10th Problem. Reducibility and
  • Rice’s Theorem.
  • Gödel Incompleteness Theorem and Computational Complexity.