lõppautomaat

Lõppautomaat, also known as a finite automaton or finite state machine (FSM), is a computational model used in computer science and theoretical computer science. It is an abstract machine that can be in exactly one of a finite number of states at any given time. The word "finite" refers to the limited number of states. The machine transitions from one state to another in response to external inputs.

A lõppautomaat consists of a finite set of states, an initial state, a set of input symbols (the alphabet), a transition function, and a set of final or accepting states. The transition function dictates which state the automaton will move to, given its current state and the input symbol it receives. The automaton starts in the initial state and processes an input string symbol by symbol. If, after processing the entire input string, the automaton is in one of the final states, the input string is considered accepted by the automaton. Otherwise, it is rejected.

Lõppautomaadid are widely used for designing digital circuits, implementing lexical analyzers in compilers, and in various areas of artificial intelligence and natural language processing. They are particularly useful for recognizing patterns in strings of symbols. There are two main types: deterministic finite automata (DFA) and non-deterministic finite automata (NFA). While NFAs can have multiple transitions for a single state-input pair or transitions on an empty string, DFAs have exactly one transition for each state-input pair and no empty string transitions. Despite their differences, DFAs and NFAs are equivalent in terms of the languages they can recognize.