Theory Of Computation

A string

An ordered n-tuple of elements from an alphabet

Determinism

Every steo of a computation follows uniquely from the preceding step

Non-Determinism

Several choices can exist for the next state at the same time

Subset Construction

The method of converting an NFA to a DFA

Chomsky’s Hierarchy

A way of categorizing languages and defining the grammars and automata required to recognise them

Types of Grammar

• Unrestricted (Type 0)

• Context-Sensitive (Type 1)

• Context-Free (Type 2)

• Regular (Type 3)

Limitations of FSA

• Cannot count symbols

• Cannot recognise languages with infinite states

• Cannot match symmetric string patterns

Kleene’s Theorem

There exists a finite automation for a language if and only if there is a regular expression for that language

The Pumping Lemma

A technique used to prove that a language is not regular

Pumping lemma proof

1. Assume L is regular. Then it has some DFA with, say, k states.

2. Pick a specific string w ∈ L that is guaranteed to be at least k symbols long (usually the language's own definition suggests an obvious candidate).

3. Split it as w = xyz obeying |xy| ≤ k and |y| ≥ 1 — but since you don't get to choose the split, you must show the contradiction holds for every possible way the adversary could split it.

4. Pump — usually setting i = 0 (remove the loop) is easiest — and show the resulting string is not in L.

5. This contradicts the pumping lemma's guarantee, so the assumption in step 1 must be false → L is not regular.