Important Terms

Length

This attribute of a string Ω is spelled as |Ω| and is equal to the number of symbols in a string.

Substring

This z of a string Ω is a string z which appears inside Ω.

Reverse

A string written in the opposite order of a string Ω.

Lexicographical Order

An order of strings as it would appear in a dictionary.

Prefix

This x of a string y exists if there is a string z such that xz = y.

Proper Prefix

This x is defined as x ≠ y, i.e. |z| ≠ 0.

Language

A set of strings over some alphabet ∑(A, B, C, L).

Alphabet

A nonempty finite set of characters (∑ = {a, b, c})

String

A finite sequence of characters.

Prefix-Free Language

Language where no member is a proper prefix of another member.

Function

An object that sets up a deterministic input-output relationship.

DFA Formal Definition

A DFA is a 5-Tuple (Q, ∑, q₀, T, ∂) where:

• Q is a finite set of states.

• ∑ is an alphabet of input symbols.

• q₀ is the start state.

• T is a subset of Q giving the accept states.

• ∂ is the transition function mathematically defined as ∂: Q x ∑ → Q that maps a state and symbol to a state.

NFA Formal Definition

An NFA is a 5-Tuple (Q, ∑, q₀, T, ∂) where:

• Q is a finite set of states.

• ∑ is an alphabet of input symbols.

• q₀ is the start state.

• T is a subset of Q giving the accept states.

• ∂ is the transition function mathematically defined as ∂: Q x ∑ → 2_Q that maps a state and symbol to a power set of states.

GFA (Generalized Finite Automaton)

An FA that consists of:

• One accept state.

• No transitions into the start state.

• No transitions outside of the accept state.

Indistinguishable

Two strings x and y are indistinguishable with respect to language L if for every string z, it holds xz ∈ L iff yz ∈ L.

Pumping Lemma (Regular)

If language L is regular, then there exists some DFA D with k states that accepts L. Additionally, for every Ω ∈ L:

• |Ω| >= k

• Ω = xyz

• y ∉ ε

• |xy| <= k

• xyⁱz ∈ L for all i >= 0
  

PDA Formal Definition

A PDA is a 6-Tuple (Q, ∑, Γ, ∂, q₀, F) where:

• Q is a finite set of states.

• ∑ is the finite input alphabet.

• Γ is the finite stack alphabet.

• ∂ is the transition function that maps a state and symbol to an action.

• q₀ is the start state.

• F is the set of accept states.

CFG Formal Definition

A CFG is a 4-Tuple (V, ∑, S, P) where:

• V is a finite set of variables.

• ∑ is a finite alphabet of terminals.

• S is the start variable.

• P is the finite set of productions where each production has the form V → (V U ∑)*

Ambiguous Grammar

A grammar that can be represented by more than 1 derivation tree.

Unambiguous Grammar

A grammar that can be represented by only 1 derivation tree.

Usable Variable

A variable that produces some string of terminals.

Nullable Variable

A variable that can generate ε.

Chomsky Normal Form

A variation of a CFG where every variable can derive exactly 2 variables and/or exactly 1 terminal, but nothing else.

Pumping Lemma (Context-Free)

If language A is context-free, then there exists a constant k such that for every string Ω ∈ A of length at least k, you can split Ω into uvxyz where:

• vy is not empty

• |vxy| <= k

• uvⁱxyⁱz ∈ A for all i >= 0

TM Formal Definition

A TM is a 7-tuple (Q, ∑, Γ, q₀, h_a, h_r, ∂) where:

• Q is a set of states.

• ∑ denotes the input alphabet.

• Γ denotes the tape alphabet.

• q₀ is the start state.

• h_a denotes the unique accept state

• h_r denotes the unique reject state

• ∂ is the transition function Q x Γ → Q x Γ x {L, R, S} that maps a state and tape letter to a state, tape letter, and head direction.

Transducer

An always-accepting TM that performs an operation on a string.

UTM

A TM that takes another TM as input and processes it.

Decidable Language

A language where it is possible to create a decider for it.

Decider

A TM that accepts all strings that are in a language and rejects all strings that are not in the language.

Turing-Recognizer

A TM that accepts all strings that are in a language and rejects or loops on all strings that are not in the language.

T-Recognizable Language

A language where it is possible to create a T-recognizer for it.

Undecidable Language

A language where it is impossible to create a decider for it.

Unrecognizable Language

A language where it is impossible to create a T-recognizer for it.

Enumerator

A TM where given an empty input tape, it can print out all of the strings in a language.

Enumerable Language

A language where it is possible to create an enumerator for it.

A_TM

{<M, w> | M accepts w} - Undecidable

HALT_TM

{<M, w> | M halts on w} - Undecidable

E_TM

{<M> | M is a TM and L(M) = ø} - Undecidable

EQ_TM

{<M₁, M₂> | L(M₁) = L(M₂)} - Undecidable

Reducibility

Language A reduces to language B (A <= mB) if there exists a computable function f (f: ∑* → ∑*), such that for every x, x ∈ A iff f(x) ∈ B.

P

The set of all problems that are decided by a DTM in polynomial time.

NP

The set of all problems that are decided by a NTM in polynomial time | The set of all problems that a DTM can verify a solution (certificate) of in polynomial time.

NP-Complete

The set of all languages/problems in NP that are all reducible to each other.

Computable Function

A function that produces an output, always works, always halts, and never loops.

CLIQUE

{<G, k> | G - graph that contains k-clique}

SAT

{<ϕ> | ϕ is a boolean formula satisfiable}

SUBSET-SUM

{<s, t> | s - set of positive integers with subset, with sum t}

PARTITION

{<s> | s - set of positive integers with subset sum of ∑s / 2}