Theory of Computing

Back to UWaterloo


1 Background

2 DFAs and Countability


4 Regular Expressions

3 regular operations:

If A and B are regular languages, any regular operations on them produce regular languages

5 Proving languages to be nonregular

How to use the pumping lemma:

  1. fix n as any number, we describe the rest of the proof based on any fixed selection of n
  2. define a string towards contradiction, that satisfies the requirements of the pumping lemma
  3. determine what form the loop must take
  4. because the pumping lemma must hold for all number of loops, show that there is a particular number of loops where xyiz is not contained in the language which contradicts the third condition of the pumping lemma.

6 More regular languages

7 Context-free grammars and languages

Prove that all w in A is generated by CFG G:

  1. Let w be a string in A, and set n = |w|. Prove that w is in L(G) by strong induction
  2. base case: n = 0 so w is empty, and show that there is some derivation
  3. induction step: assume n >= 1, and hypothesize that x in L(G) for every x in A with |x| < n
  4. use properties of language A and the assumption that any strings less are generated by G to find a derivation of w in terms of other generated strings smaller than w

8 Parse Trees, Ambiguity, Chomsky Normal Form

9 Closure Properties for context-free languages

10 Proving non-context-free

11 Pushdown Automata

12 Stack Machines

13 Stack Machine computations, languages and functions

14 Turing Machines

15 Encodings and decidable languages

16 Universal stack machines and non-semidecidable language

17 Undecidable Languages

Some undecidable languages:

Two ways to prove undecidability:

  1. contradiction
  2. reduction: A reduces to B lets us show that the decidability of B implies the decidability of A

18 Closure Properties in Decidability

TODO read this lecture more closely

19 Time-bounded Computations

20 NP, Polynomial-Time Mapping Reductions