nfa_accepts

std.seq.nfa_accepts · Level L3

Whether a nondeterministic finite automaton with ε-moves accepts a word, as 1 or 0: the subset simulation, carrying the set of reachable states as a 0/1 vector. T[σ] is the 0/1 transition relation of symbol σ, E the ε-moves, and C its reflexive transitive closure (reachability). The reference follows the sets of states directly.

accept ⇔ (S₀·∏ T_σ C) · accept > 0

Signature

nfa_accepts(T: f64[a, k, k], E: f64[k, k], start: f64[k], accept: f64[k], word: i64[L]) → f64[]

Structure

The function as NOVA stores it: one box per input, operation and output, and arrows that carry values. A double border marks another library function this one runs — called once, or by Scan once per element; select it to open that function.

input
operation
constant
call
output

Verification

Signature proven by NOVA’s shape solver, for every size.
Equal to the reference ε-closures and transitions on sets of states in exact rational arithmetic, on all 40 test cases.
All 40 float64 results are exact: the error is zero.
Interpreter and NumPy backend return bit-identical results.
At float32 too: the 40 test cases rounded to float32, and 40 of them exact, with zero error.

Accuracy in detail

correctly rounded (the float64 nearest the exact value): 100%
bit-equal to the NumPy formula in float64: 100%
largest error, in units in the last place: 0

Identity

Calls

dot reachability vecmat nfa_step

Called by

—

sha256:3f7ef308503a8d3fa6fc17408c27db40107db990dd975083f7af00d6a110084f

The semantic hash of the graph. It changes when the program changes, and never when only its documentation does.

Control handle

Symbol: Ω:std.seq.nfa_accepts · Ω:nfa_accepts
Pins: sha256:eacbe31c3cb8db048813eccc2dbec71757618e428e3860acf145005d23c661aethis graph and the 5 it reaches through calls
Evidence: sha256:5d604bc76e1621a9341baa9b69318e64040b12b3eb06ce6ebc6c8e2afad40d0dthe hash of its verification record
Needs: no capability: a pure function

Through NOVA’s control layer, the symbol launches this function only while the program still matches what it pins: a change to this graph, or to any graph it reaches, needs a migration first.