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 NP-complete problem, as proved by Stephen Cook in 1971