# Notes on TOC

**DFA, NFA**

- For a regular language we can construct more than one DFA accepting it
- Given a DFA we have only one unique regular language for that
- The expressive power of NFA and DFA are same
- We can convert NFA to DFA and equivalent NFA exist for a DFA
- DFA can be minimized
- Pumping lemma for Regular Languages is used to prove certain languages are not Regular.

**Context Free Grammar (CFG)**

- Chomsky normal form grammars are not unique. Testing equivalence of context-free grammars is known to be undecidable.
- A two-stack PDA is equivalent in computing power of a Turing machine. Which means they can accept languages that are not context free.
- PDA accepts a language by

1) Empty Stack

2) Final State

And we can convert between these two

- Pumping lemma for Context Free Languages is used to prove certain languages are not Context Free.
- Deterministic Push Down Automata accepts a set of languages between Regular Languages and Context Free Languages. Which means that there are certain Context Free Languages not accepted by Deterministic Push Down Automata
- Non Deterministic Push Down Automata (Push Down Automata) accepts all the Context Free Languages.

**Turing Machines**

- Turing Machines are countable and Languages are uncountable (by diagonalization principle). This means there exist some languages that are not computable.
- The language accepted Turing Machines is called Recursively Enumerable (RE) languages. Language accepted by turing machine which halts on all inputs is called Recursive Languages.
- Recursive languages are also called decidable. A TM for a recursive language corresponds to the notion of an algorithm. This means an algorithm (well defined set of instructions) exist for a problem only if the language is recursive.
- Halting Problem is one of the first problem to be proved undecidable.
- Reduction is the method of proving certain languages are undecidable.
- If we have a problem P1 known to be undecidable and we need to show that P2 is undecidable we can reduce
**P1 to P2**to show that P2 is undecidable. Note that the direction of reduction is__from known problem P1 to unknown problem P2__.

**Complexity Theory**

- SAT was the first known
problem, as proved by__NP-complete__in 1971__Stephen Cook__