Deterministic Finite Automaton (DFA)

Non-Deterministic Finite Automaton (NFA)

Pushdown Automaton (PDA)

Linear Bounded Automaton (LBA)

To describe a set of strings

To parse a string according to a given grammar

To generate a random string

To compress a string

Chomsky Normal Form (CNF)

Greibach Normal Form (GNF)

Regular Grammar

Context-Sensitive Grammar

For any regular language L, there exists a constant n such that any string w in L with |w| ≥ n can be divided into three substrings u, v, and x, where |v| ≥ 1, such that uv^i x is also in L for all i ≥ 0.

For any regular language L, there exists a constant n such that any string w in L with |w| ≥ n can be divided into three substrings u, v, and x, where |v| ≥ 1, such that uv^i x is not in L for all i ≥ 0.

For any regular language L, there exists a constant n such that any string w in L with |w| ≥ n can be divided into three substrings u, v, and x, where |v| ≥ 1, such that uv^i x is in L for all i ≤ 0.

For any regular language L, there exists a constant n such that any string w in L with |w| ≥ n can be divided into three substrings u, v, and x, where |v| ≥ 1, such that uv^i x is not in L for all i ≤ 0.

For any regular language L, there exists a unique minimal DFA that accepts L.

For any regular language L, there exists a unique minimal NFA that accepts L.

For any regular language L, there exists a unique minimal PDA that accepts L.

For any regular language L, there exists a unique minimal LBA that accepts L.

Union

Intersection

Concatenation

Complement

A hierarchy of formal grammars that classifies languages based on their generative power.

A hierarchy of finite automata that classifies languages based on their acceptance power.

A hierarchy of regular expressions that classifies languages based on their descriptive power.

A hierarchy of context-free grammars that classifies languages based on their parsing power.

Deterministic Turing Machine (DTM)

Non-Deterministic Turing Machine (NTM)

Universal Turing Machine (UTM)

Linear Bounded Automaton (LBA)

Any computation that can be carried out by a Turing machine can also be carried out by a human computer.

Any computation that can be carried out by a human computer can also be carried out by a Turing machine.

Any computation that can be carried out by a Turing machine can also be carried out by a quantum computer.

Any computation that can be carried out by a quantum computer can also be carried out by a Turing machine.

The Halting Problem

The Post Correspondence Problem

The Traveling Salesman Problem

The Graph Isomorphism Problem

Any non-trivial property of the set of all Turing machines is undecidable.

Any non-trivial property of the set of all regular languages is undecidable.

Any non-trivial property of the set of all context-free languages is undecidable.

Any non-trivial property of the set of all recursively enumerable languages is undecidable.

Regular Language

Context-Free Language

Context-Sensitive Language

Recursively Enumerable Language

A context-free grammar in which every production is of the form A → aB or A → a, where A and B are non-terminals and a is a terminal.

A context-free grammar in which every production is of the form A → BC or A → a, where A, B, and C are non-terminals and a is a terminal.

A context-free grammar in which every production is of the form A → aBC or A → a, where A, B, and C are non-terminals and a is a terminal.

A context-free grammar in which every production is of the form A → BC or A → a, where A and B are non-terminals and a is a terminal.

Top-Down Parsing

Bottom-Up Parsing

Left-to-Right Parsing

Right-to-Left Parsing