Állapotsgép

Állapotsgép is the Hungarian term for a finite state machine (FSM), also known as a finite automaton. It is a computational model that can exist in one of a finite number of states at any given time. The FSM can transition from one state to another in response to external inputs. This transition depends on the current state and the input received. At any given time, the FSM is in precisely one state.

An állapotsgép can be formally defined as a tuple of five elements: a finite set of states, a finite set of input symbols (the alphabet), a transition function, a start state, and a set of accept (or final) states. The transition function specifies how the machine moves from one state to another based on the input. The start state is the initial state of the machine before any input is processed. The accept states are those states that, if reached after processing all input, indicate that the input string is recognized by the machine.

Állapotsgépek are widely used in various fields, including digital circuit design, compiler construction for lexical analysis, natural language processing, and modeling of simple processes. They are particularly useful for recognizing patterns in sequential data. The behavior of an állapotsgép is deterministic if for each state and input symbol there is exactly one next state. It is non-deterministic if there can be multiple possible next states for a given state and input symbol.