Definition: Let M = (Q, Σ, δ, q0, A) be a DFA. The language L is regular if there exists a machine M such that L = L(M).
* Applications of Finite Automata *
String matching/processing
Compiler Construction
The various compilers such as C/C++, Pascal, Fortran or any other compiler is designed using the finite automata. The DFAs are extensively used in the building the various phases of compiler such as
- Lexical analysis (To identify the tokens, identifiers, to strip of the comments etc.)
- Syntax analysis (To check the syntax of each statement or control statement used in the program)
- Code optimization (To remove the un wanted code)
- Code generation (To generate the machine code)
Other applications
The concept of finite automata is used in wide applications. It is not possible to list all the applications as there are infinite number of applications. This section lists some applications:
- Large natural vocabularies can be described using finite automaton which includes the applications such as spelling checkers and advisers, multi-language dictionaries, to indent the documents, in calculators to evaluate complex expressions based on the priority of an operator etc. to name a few. Any editor that we use uses finite automaton for implementation.
- Finite automaton is very useful in recognizing difficult problems i.e., sometimes it is very essential to solve an un-decidable problem. Even though there is no general solution exists for the specified problem, using theory of computation, we can find the approximate solutions.
- Finite automaton is very useful in hardware design such as circuit verification, in design of the hardware board (mother board or any other hardware unit), automatic traffic signals, radio controlled toys, elevators, automatic sensors, remote sensing or controller etc.
- In game theory and games wherein we use some control characters to fight against a monster, economics, computer graphics, linguistics etc., finite automaton plays a very important role.
No comments:
Post a Comment