Formal Language and Applications of Automata Theory

Formal Language and Automata Theory

1. Applications of Automata
Automaton is nothing but a machine which
accepts the strings of a language L over an input
alphabet Σ.

2. Automaton
There are four different types of Automata that are mostly used in the
theory of computation. These are as follows −
Finite-state machine (FSM).
Pushdown automata (PDA).
Linear-bounded automata (LBA).
Turing machine (TM).
When comparing these four types of automata, Finite-state machines are
less powerful whereas Turing machines are more powerful.
Note 
− Deterministic Finite Automata (DFA) and the Non-Deterministic
Finite Automata (NFA) have the same power because every DFA is
converted into NFA and every NFA is converted into DFA.

3. Equivalence
Finite-state Machine is equivalent to the following
PDA with finite stack.
Turing Machine with finite tape.
Turing Machine with unidirectional tape.
Turing Machine with read only tape.
Pushdown Automata is equivalent to the following −
Finite Automata with stack
Turing Machine is equivalent to the following −
PDA with additional stack.
Finite Automata with two stacks.

4. Applications of different Automata
Finite Automata (FA)
The applications of Finite Automata are as
follows −
Design of the lexical analysis of a compiler.
Recognize the pattern by using regular
expressions.
Use of the Mealy and Moore Machines for
designing the combination and sequential
circuits.
Helpful in text editors.
Used for spell checkers.

5. Applications of different Automata
Push Down Automata (PDA)
The applications of Pushdown automata are
as follows −
Used in the Syntax Analysis phase.
Implementation of stack applications.
Used in evaluations of the arithmetic
expressions.
Used for solving the Tower of Hanoi Problem.

6. Applications of different Automata
Linear Bounded Automata (LBA)
The applications of linear bounded automata
are as follows −
Used in the genetic programming
implementation.
Construction of syntactic parse trees.

7. Applications of different Automata
Turing Machine (TM)
The applications of Turing machine are as
follows −
Used to solve the recursively enumerable
problem.
Used for knowing complexity theory.
Used for neural networks implementation.
Used in Robotics Applications.
Used in the implementation of artificial
intelligence.

8. Applications of finite automata include
string matching algorithms
network protocols
lexical analyzers

9. String Processing
Consider finding all occurrences of a short
string (pattern string) within a long string (text
string). This can be done by processing the
text through a DFA: the DFA for all strings
that end with the pattern string. Each time the
accept state is reached, the current position
in the text is output.

10. Lexical Analysis
In compiling a program, the first step is lexical
analysis.
This isolates keywords, identifiers etc., while
eliminating irrelevant symbols.
A token is a category, for example “identifier”, “relation
operator” or specific keyword.
For example,
token RE
keyword then then
variable name [a-zA-Z][a-zA-Z0-9]*
where latter RE says it is any string of alphanumeric
characters starting with a letter.

11. Applications of TM
Turing machines founds applications in algorithmic information theory
and complexity studies, software testing, high performance
computing, machine learning, software engineering, computer
networks and evolutionary computations.
Algorithms = Turing Machine
In Computer Science, the formal definition of Algorithm is that any set
of steps that can be performed by a Turing Machine. Several
researchers came up with alternative definitions but all boiled down to
the same definition using Turing Machine.
Thus, Turing Machine is the fundamental concept in Computer
Science and hence, all solutions that can be defined using an
Algorithm is using the ideas of Turing Machine and other Computing
models from Theory of Computation.

12. Real life applications of DFA:
Traffic Lights
Video Games -Pac Man is a popular game in the early 1990s.
CPU Controllers
Protocol Analysis -Transmission Control Protocol (TCP) is the
basis of Computer Networking and the possible states and
situations are designed using Automata Machine
Regular Expression Matching
Vending Machines- Vending Machines are machines installed in
a city on the side of roads at specific intervals. Citizens can
insert money into these machines and get the selected drinks
and snacks automatically and the return change was provided
by the machine as well.
Speech Recognition
Natural Language Processing