Why finite automata is used

Modern computers are a common example of an automaton. Alternatively, a regular language can be defined as a language recognized by a finite automaton. An automaton, for our purposes, is a set of rules, called transitions, which define a language by describing how strings in that language can be recognized. Finite automata, pushdown automata and Turing machines are examples. Regular expressions are a special notation for representing regular languages.

A Finite Automata FA is said to be deterministic, if corresponding to an input symbol, there is single resultant state i. Finite automata is a state machine that takes a string of symbols as input and changes its state accordingly. Finite automata is a recognizer for regular expressions. When a regular expression string is fed into finite automata, it changes its state for each literal. Role of the parser : The parser obtains a string of tokens from the lexical analyzer and verifies that the string can be the grammar for the source language.

It detects and reports any syntax errors and produces a parse tree from which intermediate code can be generated. As the first phase of a compiler, the main task of the lexical analyzer is to read the input characters of the source program, group them into lexemes, and produce as output a sequence of tokens for each lexeme in the source program.

The stream of tokens is sent to the parser for syntax analysis. A Turing machine is a finite-state machine yet the inverse is not true. The exciting history of how finite automata became a branch of computer science illustrates its wide range of applications.

The first people to consider the concept of a finite-state machine included a team of biologists, psychologists, mathematicians, engineers and some of the first computer scientists. They all shared a common interest: to model the human thought process, whether in the brain or in a computer.

Warren McCulloch and Walter Pitts, two neurophysiologists, were the first to present a description of finite automata in Their paper, entitled, "A Logical Calculus Immanent in Nervous Activity", made significant contributions to the study of neural network theory, theory of automata, the theory of computation and cybernetics. Later, two computer scientists, G. Mealy and E.

Moore, generalized the theory to much more powerful machines in separate papers, published in The finite-state machines, the Mealy machine and the Moore machine, are named in recognition of their work. While the Mealy machine determines its outputs through the current state and the input, the Moore machine's output is based upon the current state alone.

FSMs are abstract machines, consisting of a set of states set Q , set of input events set I , a set of output events set Z and a state transition function.

The state transition function takes the current state and an input event and returns the new set of output events and the next state. Therefore, it can be seen as a function which maps an ordered sequence of input events into a corresponding sequence, or set, of output events. Finite-state machines are ideal computation models for a small amount of memory, and do not maintain memory. This mathematical model of a machine can only reach a finite number of states and transitions between these states.

Its main application is in mathematical problem analysis. Finite-machines are also used for purposes aside from general computations, such as to recognize regular languages. An elevator is a mechanism that does not remember all previous requests for service but the current floor, the direction of motion up or down and the collection of not-yet satisfied requests for services.

The number of odd arrows are one greater than even, i. Transition : The transition from one state to another state happens when a desired symbol in the input is found. Upon transition, automata can either move to the next state or stay in the same state. Movement from one state to another is shown as a directed arrow, where the arrows points to the destination state.

If automata stays on the same state, an arrow pointing from a state to itself is drawn. In a DFA, for a particular input character, the machine goes to one state only. A transition function is defined on every state for every input symbol. A DFA with a minimum number of states is generally preferred. Ability to transmit to any number of states for a particular input.

If we compare both in terms of power, both are equivalent. Skip to content. Change Language. Related Articles. Regular expression, languages, grammar and finite automata.