I feel like we don’t need a novel language for this. There’s already a pretty-well-known language that’s almost a DSL for “making complex finite-state machines easy to create”: Erlang.
I know that sounds wacky, so let me pitch you on that idea :)
In ‘primitive’ Erlang (i.e. Erlang without OTP), each FSM state is just a function, that can contain its own event loop (`receive` statement) to accept input, and then can transition to a new state based on that input by tail-calling another function.
Such an Erlang module is a direct, 1:1 encoding of the FSM you’d draw on paper — and very readable as such — but is also plain-old executable Erlang code! In fact, this is basically the most idiomatic Erlang code you can write, syntactically. It’s when the language is at its best and most compact/expressive. (It’s also when all of Erlang’s weird syntax choices suddenly make perfect sense.)
You can easily author+maintain an FSM with a large/complex tree of states and sub-states, by just putting each state function with its various sub-state functions into its own module, and then having each module only expose the valid entry states for each sub-state set.
Because each independent FSM exists in its own actor (virtual thread of execution), you don’t need any more than this. You don’t need to worry about the data representation of the FSM — the FSM’s data representation is the actor’s process record + stack. And you don’t need to worry about how to “pump” the FSMs; they’re pumped by the runtime scheduler. (However, if you care about pinning down your concurrency model — e.g. if you’re trying to model a DSP — there are Erlang libraries for specific abstractions like CSP channels that you can use to do so.)
It’s very easy to write a static analysis pass to verify that a primitive Erlang module like this constitutes an FSM “and no more” — i.e. that it could be transpiled into any other formalism that instantiates an FSM (e.g. a regex; a DSP; etc.) Erlang even breaks down its compiler into helpful separate reusable components (all available to any Erlang program) to help you do this. And these components make it just as easy to do the actual transpilation, turning this Erlang code into whatever other kind of encoded formalism you like.
But, unlike most such formalism DSLs, it’s very easy to also break out of the FSM abstraction, and trade it for a more powerful one, if an FSM no longer works for your use-case. You’re working with regular Erlang code. So, if you just do a regular stack-frame-pushing call instead of a tail-call, now your FSM is a pushdown automaton. Or, if you pass a state variable on the stack along with each tail-call, now you’ve got a Turing machine.
Honestly, ignoring all the stuff about concurrency, Erlang source code / BEAM bytecode is an almost perfect abstract machine for reifying various computational formalisms in an externally-verifiable way. If I was working on a computational proof for some CS conjecture, I’d heavily consider 1. writing the problem statement in (primitive, non-OTP) Erlang, and then 2. writing a small transpiler that would convert Erlang to lemmas in Z3 or Coq. (I’ve already done this once or twice, actually.)
And, if I were implementing something like Cloudflare’s Edge Workers “but for FSMs” (e.g. some user-submitted pattern-matching automata for structured data, to filter user subscriptions to that structured data) then it’d be an extremely easy decision to standardize on (a restricted, static-analyzed at submit-time sub-ISA of) BEAM bytecode as the user-submitted program format. I would then just implement my worker server as a regular Erlang server that would load+run those checked BEAM modules.