# Automata Theory
---
1. Automata and formal languages
- prerequisite: formal-language-theory
- automaton
- determinism

Many types of automata will be introduced \emph{determinism}.
In philosophy, determinism is a viewpoint that the universe evolves in only one possible way (as opposed to our universe 'branching' into different possibilities). 


1. combination logic
- prerequisite: mathematical-logic
- Boolean circuits
1. Finite state machine (FSM)
- DFA
- NDFA
- DFA-NFA equivalence
- regular language class equivalence
1. Pushdown automata (PDA)
- PDA
- context free language class equivalence
- DPDA
- PDA-DPDA inequivalence
2. Turing machine (TM)
- Turing machine (TM)
- Turing complete model of computation
- recognizable language
- decidable language
- unrecognizable languages
- undecidable languages
- mapping reducibility
- Turing machine property
- Rice's theorem
- Rice's theorem
- nondeterministic Turing machine (NTM)