COMS W3261 CS Theory
Lecture 1: Introduction to CS Theory

1. Course Objectives

• Learning computational thinking
• Understanding the fundamental models of computation that underlie modern computer hardware, software, and programming languages.
• Discovering that there are problems no computer can solve.
• Discovering that there are limits on how fast a computer can solve a problem.
• Mastering the foundations of automata theory, computability theory, complexity theory, pac learning, and the lambda calculus.
• Learning about applications of computer science theory to algorithms, programming languages, compilers, machine learning, operating systems, and software verification.

2. Course Syllabus

• Languages and decision problems
• The Chomsky hierarchy of families of languages
• Finite automata
• Regular expressions
• Properties of regular languages
• Context-free grammars
• Pushdown automata
• Properties of context-free languages
• Algorithms and Turing machines
• Introduction to computability theory
• Introduction to complexity theory
• Introduction to probably approximately correct learning
• Introduction to the lambda calculus

3. Textbooks and References

• The course text is
John E. Hopcroft, Rajeev Motwani, and Jeffrey D. Ullman
Introduction to Automata Theory, Languages, and Computation, Third Edition
Pearson/Addison-Wesley, 2007, ISBN-10: 0321462254 | ISBN-13: 9780321462251



• Other good references are
• Michael Sipser
Introduction to the Theory of Computation, Third Edition
Cengage Learning, 2013


• Alfred V. Aho and Jeffrey D. Ullman
Foundations of Computer Science, C Edition
W. H. Freeman, 1995
An online version of this book is available here.



• Scott Aaronson and Nancy Lynch
6.045J Automata, Computability, and Complexity, Spring 2011
MIT OpenCourseWare

4. Course Requirements

• Homeworks — best four out of five homeworks will constitute 15% of final grade
• Midterm — 40% of final grade
• Final — 45% of final grade

5. Languages

• Precise definitions are very important in theory. We start by giving definitions for some of the most fundamental concepts in CS theory beginning with alphabets, strings, and languages.
• An alphabet Σ is a finite, nonempty set of symbols.
• Example alphabets: {0,1}, ASCII, Unicode
• A string is a finite sequence of symbols chosen from some alphabet.
• Example strings: ε (the empty string), 0, 01, 011
• Common operations on strings: concatenation, reversal
• Terms associated with strings: prefix, suffix, substring, subsequence
• A language over Σ is a set of strings whose symbols are chosen from Σ. Examples:
• the empty set, ∅
• {0,1}
• P = {10, 11, 101, 111, 1011, 1101, ... } (the binary representations of the prime numbers)
• The set of all syntactically valid Java programs.
• The set of all valid English sentences?
• Operations on languages
• New languages can be created by applying operators of various kinds to languages.
• Example language operator: The Kleene closure of the language {0,1} is denoted (0,1}* and it is the language {ε, 0, 1, 00, 01, 10, 11, 000, ... }, which consists of all strings of 0s and 1s including the empty string.
Question: How many strings are there in {0,1}*?
• A problem is the question of deciding whether a given string is a member of some particular language.
• Example problem: Given a binary number x, is x in P?

6. Proofs

• What is a theorem?
• A theorem is a statement that has been proven true by a convincing logical argument.
• What is a proof?
• A (deductive) proof is a sequence of statements each one of which is a given fact or follows by a logical rule from some previous statements in the proof.
• Types of proof
• By deduction
• By construction
• By induction
• By structural induction
• By contradiction
• Many others

7. Practice Problems

1. How many strings over {0,1} are there?
2. How many languages over {0,1} are there?
3. How many (a) prefixes, (b) suffixes, (c) substrings, (d) subsequences are there in a string of length n?
4. What does it mean for a string to have balanced parentheses?
5. Prove that the following recursive definition generates all and only all strings of balanced parentheses. Hint: Use induction on the length of a string to show that every balanced string of length 2n is generated by the definition and use induction on the number n of rules used to generate a string to show that every string generated by the grammar is a string of balanced parentheses.
• Rule 1 (basis): The empty string is a balanced string.
• Rule 2 (induction): If x and y are balanced strings, then (x)y is a balanced string.
See pp. 64-68 of Chapter 2 of Aho and Ullman, Foundations of Computer Science for an answer to this practice problem.
6. Use contradiction to show that the square root of two is not a rational number.
7. Research problem: If x is a string of length m and y is a string of length n, then what is the maximum possible number of longest common subsequences between x and y as a function of m and n?

8. Reading Assignment

• HMU: Ch. 1