1.1.1 Deterministic Finite Automaton DFA

A deterministic finite automaton DFA is a 5-tuple:

$(Q,\mathrm{\Sigma },\delta ,q_0,F)$

where:

• $Q$ is a finite set of states
• $\mathrm{\Sigma }$ is an alphabet
• $\delta$ is a transition function described as $\delta :Q\times \mathrm{\Sigma }\to Q$
• $q_0\in Q$ is the initial state
• $F\subseteq Q$ is a subset of states called accept states

1.2.1 Pushdown Automaton PDA

A pushdown automata PFA is a 6-tuple:

$(Q,\mathrm{\Sigma },\mathrm{\Gamma },\delta ,q_0,F)$

where:

• $Q$ is a finite set of states
• $\mathrm{\Sigma }$ is an alphabet
• $\mathrm{\Gamma }$ is the stack alphabet
• $\delta$ is a transition function described as $\delta :Q\times \mathrm{\Sigma }\times \mathrm{\Gamma }\to P(Q\times {\mathrm{\Gamma }}_{ϵ})$
• $q_0\in Q$ is the initial state
• $F\subseteq Q$ is a subset of states called accept states

1.3.1 Basic Turing Machine

A Basic Turing Machine is a 7-tuple:

$(Q,\mathrm{\Sigma },\mathrm{\Gamma },\delta ,q_0,q_{accept},q_{reject})$

where $Q,\mathrm{\Sigma },\mathrm{\Gamma }$ are all finite sets and:

• $Q$ is a set of states
• $\mathrm{\Sigma }$ is an alphabet not containing the blank symbol $\bigsqcup$
• $\mathrm{\Gamma }$ is the tape alphabet, where $\bigsqcup \in \mathrm{\Gamma }$ and $\mathrm{\Sigma }\subseteq \mathrm{\Gamma }$
• $\delta$ is a transition function described as $\delta :Q\times \mathrm{\Sigma }\to Q\times \mathrm{\Gamma }\times \{L,R\}$
• $q_0\in Q$ is the initial state
• $q_{accept}\in Q$ is the accept state
• $q_{reject}\in Q$ is the reject state, where $q_{reject}\ne q_{accept}$

1.4.1 Linear-Bound Automaton (LBA)

To continue.