State (computer science)
Encyclopedia
In computer science
and automata theory
, a state is a unique configuration of information in a program or machine. It is a concept that occasionally extends into some forms of systems programming
such as lexer
s and parsers.
Whether the automaton
in question is a finite state machine
, a pushdown automaton
or a full-fledged Turing machine
, a state is a particular set of instructions that will be executed in response to the machine's input. The state can be thought of as analogous to a practical computer's main memory. The behavior of the system is a function of
Following states are distinguished:
In information processing
, a state is the complete set of properties (for example, its energy level
, etc. see state (physics)) transmitted by an object to an observer
via one or more channels
. Any change in the nature or quantity of such properties in a state is detected by an observer and thus a transmission of information
occurs.
An information system
or protocol that relies upon state is said to be stateful. One that does not is said to be stateless. For example, there are stateless firewalls and stateless server
s, and HTTP is considered a stateless protocol. A character encoding
such as ISO 2022 is said to be stateful, if the interpretation of a particular code value depends on the code values that came before it.
Computer science
Computer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...
and automata theory
Automata theory
In theoretical computer science, automata theory is the study of abstract machines and the computational problems that can be solved using these machines. These abstract machines are called automata...
, a state is a unique configuration of information in a program or machine. It is a concept that occasionally extends into some forms of systems programming
System programming
System programming is the activity of programming system software. The primary distinguishing characteristic of systems programming when compared to application programming is that application programming aims to produce software which provides services to the user System programming (or systems...
such as lexer
Lexical analysis
In computer science, lexical analysis is the process of converting a sequence of characters into a sequence of tokens. A program or function which performs lexical analysis is called a lexical analyzer, lexer or scanner...
s and parsers.
Whether the automaton
Automaton
An automaton is a self-operating machine. The word is sometimes used to describe a robot, more specifically an autonomous robot. An alternative spelling, now obsolete, is automation.-Etymology:...
in question is a finite state machine
Finite state machine
A finite-state machine or finite-state automaton , or simply a state machine, is a mathematical model used to design computer programs and digital logic circuits. It is conceived as an abstract machine that can be in one of a finite number of states...
, a pushdown automaton
Pushdown automaton
In automata theory, a pushdown automaton is a finite automaton that can make use of a stack containing data.- Operation :Pushdown automata differ from finite state machines in two ways:...
or a full-fledged Turing machine
Turing machine
A Turing machine is a theoretical device that manipulates symbols on a strip of tape according to a table of rules. Despite its simplicity, a Turing machine can be adapted to simulate the logic of any computer algorithm, and is particularly useful in explaining the functions of a CPU inside a...
, a state is a particular set of instructions that will be executed in response to the machine's input. The state can be thought of as analogous to a practical computer's main memory. The behavior of the system is a function of
- the definition of the automaton,
- the input, and
- the current state.
Following states are distinguished:
- Compatible states are states in a state machine that do not conflict for any input values. Thus for every input, both states must have the same output, and both states must have the same successor (or unspecified successors), or both must not change. Compatible states are redundant, if occurring in the same state machine.
- Distinguishable states are states in a state machine that have at least one input sequence causing different output sequences - no matter which state is the initial state.
- Equivalent states are states in a state machine which, for every possible input sequence, the same output sequence will be produced - no matter which state is the initial state.
In information processing
Information processing
Information processing is the change of information in any manner detectable by an observer. As such, it is a process which describes everything which happens in the universe, from the falling of a rock to the printing of a text file from a digital computer system...
, a state is the complete set of properties (for example, its energy level
Energy level
A quantum mechanical system or particle that is bound -- that is, confined spatially—can only take on certain discrete values of energy. This contrasts with classical particles, which can have any energy. These discrete values are called energy levels...
, etc. see state (physics)) transmitted by an object to an observer
State observer
In control theory, a state observer is a system that models a real system in order to provide an estimate of its internal state, given measurements of the input and output of the real system. It is typically a computer-implemented mathematical model....
via one or more channels
Channel (communications)
In telecommunications and computer networking, a communication channel, or channel, refers either to a physical transmission medium such as a wire, or to a logical connection over a multiplexed medium such as a radio channel...
. Any change in the nature or quantity of such properties in a state is detected by an observer and thus a transmission of information
Information
Information in its most restricted technical sense is a message or collection of messages that consists of an ordered sequence of symbols, or it is the meaning that can be interpreted from such a message or collection of messages. Information can be recorded or transmitted. It can be recorded as...
occurs.
An information system
Information system
An information system - or application landscape - is any combination of information technology and people's activities that support operations, management, and decision making. In a very broad sense, the term information system is frequently used to refer to the interaction between people,...
or protocol that relies upon state is said to be stateful. One that does not is said to be stateless. For example, there are stateless firewalls and stateless server
Stateless server
In computing, a stateless protocol is a communications protocol that treats each request as an independent transaction that is unrelated to any previous request so that the communication consists of independent pairs of requests and responses...
s, and HTTP is considered a stateless protocol. A character encoding
Character encoding
A character encoding system consists of a code that pairs each character from a given repertoire with something else, such as a sequence of natural numbers, octets or electrical pulses, in order to facilitate the transmission of data through telecommunication networks or storage of text in...
such as ISO 2022 is said to be stateful, if the interpretation of a particular code value depends on the code values that came before it.
See also
- Clumping (computer science)
- Finite state machineFinite state machineA finite-state machine or finite-state automaton , or simply a state machine, is a mathematical model used to design computer programs and digital logic circuits. It is conceived as an abstract machine that can be in one of a finite number of states...
(FSM) - Mode (computer interface)Mode (computer interface)In user interface design, a mode is a distinct setting within a computer program or any physical machine interface, in which the same user input will produce perceived different results than it would in other settings....
- Program stateProgram stateOne of the key concepts in computer programming is the idea of state, essentially a snapshot of the measure of various conditions in the system. Most programming languages require a considerable amount of state information in order to operate properly - information which is generally hidden from...
- State diagramState diagramA state diagram is a type of diagram used in computer science and related fields to describe the behavior of systems. State diagrams require that the system described is composed of a finite number of states; sometimes, this is indeed the case, while at other times this is a reasonable abstraction...