Finite Languages & Automata

Sequence

A potentially infinite, ordered list of objects, separated by commas.

Example: 4, 2, 3, 4

Tuple

A finite sequence surrounded by parentheses.

Example: (4, 2, 3, 4)

String (or Word)

A finite sequence of characters from a given alphabet.

Alphabet

A non-empty set of symbols/letters, denoted Σ or Γ

Substring

A sequence of symbols appearing contiguously within a string.

Concatenation

Operation joining 2 strings together - xy.

KIeene Star

Operation, generating all possible finite strings with a given alphabet.

Deterministic Finite Automaton (DFA)

A 5-tuple (Q, Σ, δ, q₀, F)

• Q = Set of states

• Σ = Alphabet

• δ = Transition function

  • δ: Q x Σ → Q

• q₀ = Start state

• F = Set of accepting states.

DFA Acceptance Conditions

Let M = (Q, Σ, δ, q0, F) be a deterministic finite automaton and let w = w₁ ... w_n be a string where w_i ∈ Σ. The automaton M accepts w if a sequence of states r₀, ... , r_n ∈ Q exists such that:

1. r₀ = q₀ (sequence begins at the start state)

2. δ(r_i, w_i+1) = r_i+1 for 0 <= i < n (each symbol transitions to the next state)

3. r_n ∈ F (accepts at the end)

Automaton recognises a language

For automaton M and language A, if A = {w | M accepts w}, i.e. if A = L(M).

Regular Language

A language recognised by a DFA, NFA, or Regular Expression.

Formal Definition of Computation of Automata

For a given automaton M, and input string w, the sequence of states that M transitions through while processing w, starting from the start state and ending at an accepting state.

Nondeterministic Finite Automaton (NFA)

A 5-tuple (Q, Σ, δ, q₀, F)

• Q = Set of states

• Σ = Alphabet

• δ = Transition function

  • δ: Q x Σ_ε → P(Q)

• q₀ = Start state

• F = Set of accepting states.

Power Set Construction Method (NFA to DFA)

Draw power set of states

DFA start = NFA start + epsilon transitions

For each element in each state, write where each one can go, e.g. ‘q0 can go to q1 or q2 via 0, nowhere via 1’.

After writing each possible transition, group them up to form transitions

Language Operations

Complement

Union

Intersection

Concatenation

Kleene Star

Complement of Language A

{w | w ∉ A}

Union of Languages A and B

{w | w ∈ A or w ∈ B}

Intersection of Languages A and B

{w | w ∈ A and w ∈ B}

Concatenation of Languages A and B

{xy | x ∈ A and y ∈ B}

Kleene Star of Language A

{x₁×₂ … ×_k | k >= 0 and x_i ∈ A}

e.g.

if A = {a, b},

A* = {ε, a, b, aa, ab, ba, bb, aaa, …}

Closure Definition (for a language class)

A language class is closed with respect to a k-ary operation if when applying the operation to k languages, the resulting language is also in the class.

Method to prove closure

Decide what to construct based on language class

• Regular → DFA/NFA

• Context-Free → Pushdown Automaton

Construct tuple using the given languages.

Product Automaton

An automaton in which the set of states is the Cartesian Product of the constituent automata.

Regular Expression

• a, where a ∈ Σ

• ε (empty)

• ∅

• R₁ ∪ R₂

• R₁ . R₂

• R*

Regular Expressions and Regular Languages

A language is regular if and only if a regular expression describes it.

Generalised Nondeterministic Finite Automaton (GNFA)

NFA that allows transitions with regular expressions.

A 5-tuple where the transition function is defined as

δ : (Q\ {qaccept) × (Q \ {qstart}) → R})

So transitions are regular expressions, not allowed into start state or out of accept state.

Converting DFA to Regular Expression method

• Add a new start and accept state.

• Transfer starting and ending transitions, e.g.

  • q_start -ε→ q₀

  • q_start -∅→ q_{not_start}

  • q₁ -ε→ q_end

• Collapse each state until only one transition remains using, for every other transition:

  • (input)(loop) ∗ (output) ∪ (across)

Pumping Lemma (Regular Languages)

If A is a regular language, any string, s, of at least pumping length, p, from A, can be split into s = xyz, where:

• For i >= 0, xyⁱz ∈ A

• |y| > 0

• |xy| > p

Context-free Grammar

A 4-tuple (V, Σ, R, S), where:

• V is the set of variables

• Σ is the set of terminals

• R is the set of rules, each rule being a variable mapping to variables and/or terminals

• S is the start variable

Context-free Language

A language that is generated by a context-free grammar.

The set of strings eventually derived from the start variable.

Chomsky Normal Form (CNF)

A form for a context-free grammar where all rules are of the form A → BC or A → a, except B and C are not the start variable, and S → ε is permitted.

Pushdown Automaton (PDA)

A 6-tuple (Q, Σ, Γ, δ, q₀, F), where:

• Q is a finite set of states

• Σ is the input alphabet

• Γ is the stack alphabet

• δ: Q x Σ x Γ_ϵ → P(Q × Γ_ϵ) is the transition function

• q₀ is the start state

• F is the set of accepting states.

Pumping Lemma (Context-free Languages)

If A is a context-free language, any string, s, of at least pumping length, p, from A, can be split into s = uvxyz, where:

• For i >= 0, uvⁱxyⁱz ∈ A

• |vy| > 0

• |vxy| <= p