\part{Fundamentals}







\chapter{Basics of automata theory}

Automaton is a theoretically defined machine. Many different automata exist and exhibit varying behaviour.

Acceptors are a type of automaton whuch take a word in a formal language and define a language by all the 'accepted words'.


A language is recognizable by some type of acceptor if there exists an acceptor of that type for which the language is its recognized language.

Many types of automata will be introduced that satisfy and violate \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). 



Despite all this, in automata theory it is perfectly fine and reason about abstract machines irrespective of actual implementations.


1. combination logic
- prerequisite: mathematical-logic
- Boolean circuits
1. Finite state machine (FSM)
- DFA

\chapter{Finite-state automata}

\begin{definition}[Deterministic finite-state automaton (DFA)]
A \emph{DFA} $D$ is a 5-tuple $(\Sigma, S, s_0, \delta, F)$ of the following.
\begin{itemize}
	\item $\Sigma$ is the input alphabet
	\item $S$ is a finite, nonempty set of states
	\item $s_0 \in S$ is the initial state
	\item $\delta : S \times \Sigma \to S$ is the state-transition function
	\item $F \subseteq S$ is the set of final states
\end{itemize}
\end{definition}

- NDFA
- DFA-NFA equivalence
- powerset construction algorithm
- regular language class equivalence



\chapter{Pushdown automata}

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)