Theory of Computation

What are automata?

Automaton is something inorganic that acts of its own volition. Essentially it just follows a set of rules.

Deterministic Finite Automata

A Deterministic Finite Automata (DFA) is a specific type of Finite State Machine(FSM).

DFAs is use for recognising regular patterns, like checking if a password starts with a pattern. If the DFA ends in an “accept” state after reading the input the string is accepted. Otherwise it is rejected.

Pushdown Automata (PDA)

We can think of PDA as a DFA with memory. It is like the DFA but with a stack memory in which you can push or pop from. PDAs are able to recognise context-free languages, which is like the syntax for most of the programming languages.

Turing Machines

A Turing Machine is an abstraction of the modern computer. Meaning that it is essentially in the same class of computation power (taken time out, but what it can actually compute no matter how long the time) as modern computer.

TMs can represent any algorithm, in fact the definition of computable is that it can be computed by a TM.

The Turing machine has:

• an infinite tape which acts as the memory that you can write symbols on

• head that can read and write on the tape and move left or right

• It changes state based on its current state (head position) and what it reads to decide where to go next.

Decidability and Recognisability

In ToC the queststions we ask are about the limits of computation. The two core things are:

• Decidability: Can the machine gives us a definite yes or no answer
• Recognisability: Can the machine gives us at least a yes answer

Decidability

A language is decidabile fi there exists a TM that can give it a yes or not answer for any input and in finite time.

• If $w\in L$ then $M$ accepts $w$
• If $w\notin L$ then $M$ rejects $w$
• $M$ halts on every input

Recognition

A language is recognisable if there exists a TM that can tell when an input is in the language. On the contrary it might run forever if the input is not in the language. Note that here we do not know whether it will eventually accept or run forever.

• If $w\in L$, then $M$ accepts $w$
• If $w\notin L$ then $M$ may reject $w$ or loops

Classes of Languages

The Figure shows the encapsulation of each language classes.

Regular Languages (RL)

RL is the easiest for the machine to recognise, as they do not require any memory or previous state information.

Context Free Languages (CFG)

As mentioned these are the classes of languages that is associated with programming languages.

Turing Decidable Languages

These problems that a TM can solve, which will give you a definite yes or no and always halts.

Turing Recognisable Languages

These problems where a machine can recognise that an input is in the language but may not halt when the input is not in.

Connection to Compilers

You can think of these concepts as foundations for the modern science of computing. A connection to compilers is that DFA is used for tokenisation (regex) and PDA is used for parsing the language of the code.