Considering finite automata as a set of states with well defined transition function, how will one formally define the element 'state' in an automaton?
As Joachim has explained: formally a state is just a member of a set. There is no structure behind this and no meaning either as long as we really stay in the domain of finite automata. just like the "state" of a computer memory does not have any meaning as long as it is not interpreted in some way as data that represents or relates to real-world entities.
Through my experience, I believe you may define 'state of an finite automaton' as "either a point between two distinct events or an end-point of a transition".
A state defines a property of the system at any given point of time.
- This is the definition given a senior professor.
Time in this context refers to time in a discrete system - a notable change between two explicit events.
A state of a finite automaton (FA) is a configuration of the dynamic entities of the underlying system. Usually, a FA is considered as a modeling framework for discrete event system. Since these systems are dynamic in nature, there variables evolve with time and thus a configuration of the values of these variables is a state of the system. Consider an example of two genes network where each gene can be considered as a Boolean variable. Now each gene has two values or states i.e. 0 and 1 and the behavior of a gene can be modeled as a two state FA. At any instant of time, the state of a gene can be either 0 or 1. On the other side, the set of states of the network will have four states: (0,0), (1,0),(0,1) and (1,1). Thus the automaton of the network will evolve within these four states depending on the order of activation and inhibition (events).
We need to be careful with terminology here. My impression is that state and configuration are sometimes mixed here. The states are really just the elementary building blocks or units of the automaton. Which states are currently active / which state the automaton is in is called a configuration. For deterministic automata this consists only of one state (and the current position of the read head on the input), for non-deterministic automata this can be several states.
- Badges
- Science topic
- Similar topics
- Computer Science