Finite Automata, Part 4

I. Quick Summary

• A. δ( q, a ) is the atomic version of the closure function. q ∈ S; a is symbol from alphabet Σ. Pronounced lower-case delta.
• B. MOVE( S, a ) if the set-level version of the closure function. S ∈ Q
• C. E() is the set-level 𝜖-closure function (lower case epsilon closure). It’s used to only find 𝜖-transitions from the input states.
• D. Using above nomenclature, A. and B. are used in the first part of subset construction. C. is used for the final 𝜖-closure calculation.

II. Details on A, B, C

A. δ( q, a )

• Accepts Singleton input. This is the atomic version of the MOVE() operator below.
• In an NFA, the delta transition function has:
  • Domain = cartesian product of Q × Σ.
  • Co-domain = power set of Q aka P( Q ).

B. MOVE( S, a )

• Accepts Set-level input. The set-level version of the δ() atomic function above.
• The collective union of all the smaller δ( q, a ) functions applied to the states q ∈ S.
• Formally:
  • MOVE( S, a ) = ∪ _{q ∈ S} δ( q, a ).
  • this is easier to read in the handwritten notes from 2/28/2026, Section 7.1.7.

C. E(S) 𝜖-closure function

• See also JH notes #2, 2/28/2026, Section 7.1.8.2 (take two on next page).
• Let S ∈ Q where Q = set of all states in the FA.
• The set-level 𝜖-closure function E() accepts as input any set S ∈ P( Q ) where P( Q ) denotes the power set of Q.
• E( S ) outputs all states p which are elements of Q such that there exists some q ∈ S which can reach p via 0, 1, 2, … n 𝜖-transitions (“free moves”, aka a transition that consumes no input symbols).
  • Note: because n = 0, 1, 2, …, this means that when n = 0, every q ∈ S is also contained in E( S ).
• Formally:
  • E( S ) = { p ∈ Q | ∃ q ∈ S such that q ⇒ p.}
  • Where the double arrow ⇒ means reaches p via n 𝜖-transitions and n = 0,1,2,3,…