ICS 355: Theory Of Computing

​

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: 
ICS 253: Discrete Structures I
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 reduction, 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.