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.

Improve this question
$\endgroup$

2 Answers 2

Reset to default
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$.

Improve this answer
$\endgroup$
2
  • $\begingroup$ What's wrong with a simple multidimensional array? $\endgroup$
    – David Richerby
    Jun 5, 2018 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, 2018 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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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