Theory of Computation

Type 0 in Chomsky Hierarchy is

Language (Recursively Enumerable Language)

Type 1 in Chomsky Hierarchy is

Language (Context-Sensitive Language)

Type 2 in Chomsky Hierarchy is

(Context-Free Language)

Type 3 in Chomsky Hierarchy is

Regular Language

Finite Automaton is

A computational model with a finite number of states and no auxiliary memory.

Pushdown Automaton (PDA) is

A computational model that extends a finite automaton with a single stack

Linear Bounded Automaton (LBA) is

A restricted Turing machine whose tape usage is limited to a linear function of the input size

Turing Machine

A mathematical model of computation with an infinite tape that defines the limits of computability.

Recursive Language (Decidable Language)

A language for which a Turing machine halts on all inputs and correctly accepts or rejects.

Recursively Enumerable Language (Recognizable Language)

A language for which a Turing machine halts and accepts strings in the language but may loop forever on strings not in the language.

Decidable

A property of a problem for which an algorithm always halts with a yes or no answer

Recognizable

A property of a problem where yes instances can be confirmed, but no instances may not halt.

Halting Problem

The problem of determining whether a program halts on a given input

Undecidable Problem

A problem for which no algorithm exists that correctly decides all instances.

Diagonalization

A proof technique using self-reference to show that certain problems cannot be decided by any algorithm.

Problem Reduction

A method of transforming one problem into another to compare their computational difficulty

Many-One Reduction (Mapping Reduction)

A reduction where instances of one problem are computably transformed into instances of another.

Undecidability via Reduction

A proof technique where a known undecidable problem is reduced to another problem to show it is also undecidable

Nondeterministic Automaton

A computational model that may have multiple possible transitions for a given state and input

Deterministic Automaton

A computational model with exactly one transition for each state and input symbol.

Nondeterministic Turing Machine (NTM)

A Turing machine that may choose among multiple transitions at each step.

Deterministic Turing Machine (DTM)

A Turing machine with exactly one transition for each state and tape symbol.

DFA = NFA result means

Deterministic and nondeterministic finite automata recognize the same class of languages.

DTM = NTM (in power) means

Deterministic and nondeterministic Turing machines recognize the same class of languages.

DPDA ⊂ NPDA means

Nondeterministic pushdown automata recognize strictly more languages than deterministic ones.

Pumping Lemma

A property that all sufficiently long strings in a language must satisfy if the language belongs to a certain class.

Pumping Length (p)

A constant such that all strings of length at least p can be pumped.

Pump i = 0

Removing the pumpable parts of a string

Pump i = 2

Repeating the pumpable parts of a string once

Contradiction (Pumping Lemma)

Showing that pumping produces a string not in the language, proving the language is not in that class.

Comparable Problems

Problems whose computational difficulty can be related through reductions.

Equivalence Class (Problems)

A set of problems that can all be reduced to one another.

Computational Power

The class of problems a computational model can solve.

Computability

The study of what problems can and cannot be solved by algorithms.

Expressive Power

The ability of a computational model to recognize complex languages.

Guaranteed Halting

The property that a machine stops on all inputs

Semi-Decidable

A problem where only yes instances are guaranteed to halt.