2
$\begingroup$

When I read the word "state" I think of a global object with a bunch of properties like the "application state". But it seems that in automata that the state is pretty much just an empty value.

Wondering what specifically the data structure is for automata states in general.

For example, the following comes from here:

An alternating register automaton over A consists of: a finite set $Q$ of states with a distinguished initial state $q_0 ∈ Q$ and a set of accepting states $F ⊆ Q$, a finite set $R$ of registers, and a transition function $$δ : Q×A×Tests(\mathscr{R}) → B+(Q×P(\mathscr{R}))$$...

Register automata have a "memory" which I associate with state, but it seems clear it is separate from the actual states in $Q$. Just looking for the data structure for state, if it's just an incremented integer, a string label, or something else, typically.

$\endgroup$
2
$\begingroup$

A proper data structure can be a dictionary (a hash table). This can be done by encoding $Q\times A \times Tests(R)$ into a string like $q\#a\#t$ as a key that $q\in Q$, $a\in A$ and $t \in Tests(R)$. And the value of the key would be the result of transition function $\delta$.

$\endgroup$
  • $\begingroup$ What's wrong with a simple multidimensional array? $\endgroup$ – David Richerby Jun 5 '18 at 18:04
  • 1
    $\begingroup$ That's a data structure for a state machine. The data structure for a state is an enum (or small integer). (A compressed array is probably a better data structure for the state machine, but a hash table could work.) $\endgroup$ – rici Jun 5 '18 at 21:38
3
$\begingroup$

As you say, the state of an automaton is just an abstract, unstructured value. As such, you don't need a data structure per se: you just need a variable type that can store different values, such as an integer.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.