What is the Theory of Computation?

• The study of abstract models of computation
• Focus on understanding the limits of computation
• Spin-off applications: regular expressions, parsing

An abstract model of a computational process

• The process takes as its input a sequence of symbols.
• The process produces a sequence of symbols as its output.

More about sequences of symbols

• An alphabet Σ is a set of symbols.
• A sequence of symbols chosen from some alphabet is a string.
• A computation uses an input alphabet Σ_input and an output alphabet Σ_output. These may be the same alphabet, or they may differ.
• A universe is the set of all possible strings that can be formed from an alphabet.

A decision algorithm

• This is a simpler kind of computational process, which will be easier to study.
• Decision algorithms are still rich enough to be interesting.
• Since this type of algorithm only deals with inputs, we only have to worry about the input alphabet, Σ.

Languages and deciders

• A language is a set of strings formed from an input alphabet Σ.
• A language is typically a subset of the universe of strings generated by Σ.
• Given a language L an algorithm decides the language if it produces the output yes if and only if its input x ∈ L.

The finite state machine

Σ = {0,1}

L = { x | x contains an odd number of 1s }

Another example

L = { x | x contains the substring 010 }

Formal definition

A finite automaton is a tuple {Q, Σ, δ, q₀, F } where

1. Q is a finite set called the states,
2. Σ is a finite set called the alphabet,
3. δ : Q × Σ → Q is the transition function,
4. q₀ ∈ Q is the start state, and
5. F ⊆ Q is the set of accept states.

A language L is a regular language if some finite automaton M recognizes L.