Coordinator: Stephanie Schwartz
Introduction to theory of computation. Topics include finite state automata, regular languages and grammars, pushdown automata, context-free languages and grammars, Turing machines, limits on algorithmic computation. Offered in spring.
C- or higher in CSCI 140 and CSCI 162.
- Understating of various proof techniques. In particular, proofs by mathematical induction. Be able to demonstrate the ability to carry out proofs by induction for simple problems.
- Define, interpret, and construct deterministic finite-state automata and non-deterministic finite-state automata; define, interpret, and construct regular expressions; apply these formalisms to practical programming problems.
- Define, interpret, and construct context free grammar; define, interpret, and construct deterministic pushdown automata and non-deterministic pushdown automata; apply these formalisms to practical programming problems.
- Explain the history, scope, and limits of Artificial Intelligence. Discuss and understand the social, ethical, legal, and philosophical aspects of Al; not only be knowledgeable about various application areas of AI but also be able to use AI tools.
- Understand parsing techniques and study their application to theory of compiler design.
- Understand the concept of Turing machines and their applications to computability.
- Explain the concepts of computable function, the universal machine, the decision problem, and the difference between decidable and undecidable problems.
Major Topics Covered
- Formal Languages
- Alphabets and strings
- Operations on strings
- Operations on languages
- Formal Grammars
- Phrase structure grammars
- Types of grammars and languages
- Relationship between grammar and language types
- Finite State Automata (FSA)
- Deterministic Finite State Automata (DFSA)
- Nondeterministic Finite State Automata (NFSA)
- Equivalent automata
- Equivalence of NFSA and DFSA
- Finite State Languages (FSL)
- Equivalence of FSL and regular languages
- Properties of Regular Languages
- Regular expressions (RE)
- Equivalence of RE and FSA
- Determining whether or not languages are regular
- Pushdown Automata (PDA)
- Deterministic Pushdown Automata (DPDA)
- Nondeterministic Pushdown Automata (NPDA)
- Non-equivalence of NPDA and DPDA
- Equivalence of NPDA and context-free languages
- Context-Free Languages (CFL)
- Relationship of CFL to regular languages
- Relationship of nondeterministic CFL to deterministic CFL
- Determining whether or not languages are context-free
- Top-Down Parsing
- Bottom-Up Parsing
- Turing Machines (TM)
- Deterministic Turing Machine (DTM)
- Nondeterministic Turing Machine (NTM)
- Equivalence of DTM and NTM
- TM to recognize languages
- TM to evaluate functions
- I. Non-computability
- Church's Thesis
- The Halting Problem
- Unsolvable Problems About Turing Machines
- Unsolvable Problems About Grammars
- Computational Complexity
- Time Complexity
- Space Complexity
- The Classes P and NP
Sample Laboratory Projects