Finite Automata

automaton/automata

a mathematical model of a computing device

languages

sets of strings

strings

finite sequences of characters

characters

individual symbols

alphabets

sets of characters

modeling memory & algorithm

machines that receive input, input provided sequentially, input causes the device to change configuration, we read off an answer

finite automata

has a finite number of states and memory, needs a start state, each state is linked by transitions - has accepting states that say YES and rejecting states that say NO to the input

alphabet (Σ = {…})

finite, nonempty set of characters/symbols

a string over alphabet (Σ)

a finite sequence of characters from the alphabet Σ

empty string (ε)

no characters

language over Σ

a set (L) of strings over Σ, including ε (said as “L is a language over Σ when L ⊆ Σ*”)

Σ*

the set of all strings of letters in Σ

language of A (ℒ(A)}

the set of strings over Σ that A accepts: ℒ(A) = { w ∈ Σ* | A accepts w }

DFA

Deterministic Finite Automaton: A DFA is defined relative to some alphabet Σ. For each state, there is EXACTLY ONE transition defined for each symbol in Σ (Deterministic). There is a unique start state. There are zero or more accepting states.

regular language

A language L when there exists a DFA D such that ( ℒ(D)) = L. (If L is a language and ( ℒ(D)) = L, we say that D recognizes the language L)

complement of a language (L bar)

Given a language L ⊆ Σ*, a complement is the language of all strings in Σ* that aren't in original language L. | L = Σ* - L

NFA

Nondeterministic Finite Automaton - there may be any number of transitions defined for each symbol in Σ, plus any number of ε-transitions. Unique start state. Zero or more accepting states. EXTRA: nondeterministic machines are magical where they can guess choices that lead to an accepting state

model of computation is deterministic

when there is exactly one choice that can make

model of computation is nondeterministic

if the computing machine has a finite number of choices available to make at each point, possibly including zero.

ε-transition

doesn’t consume any input! “free lunch”

NFA vs DFA

an NFA is a DFA that can be in many different states. at each point, when the NFA follows a transition, it tries all options at the same time. it accepts if any of the states are accepting at the end. if not, rejects. ANY LANGUAGE ACCEPTED BY A DFA CAN BE ACCEPTED BY AN NFA. EVERY DFA IS AN NFA!! if you can build an NFA, you can build a DFA for it.

subset construction

the procedure to turn an NFA into a DFA for a language L

Union L1 and L2

Theorem: If L₁ and L₂ are regular, so is L₁ ∪ L₂.

Intersection L1 and L2

Theorem: If L₁ and L₂ are regular, so is L₁ ∩ L₂.