Applications of various Automata

Automata is a machine that can accept the Strings of a Language L over an input alphabet Σ . So far we are familiar with the Types of Automata. Now, let us discuss the expressive power of Automata and further understand its Applications.

Expressive Power of various Automata: The Expressive Power of any machine can be determined from the class or set of Languages accepted by that particular type of Machine. Here is the increasing sequence of expressive power of machines :

FA < DPDA < PDA < LBA < TM

As we can observe that FA is less powerful than any other machine. It is important to note that DFA and NFA are of same power because every NFA can be converted into DFA and every DFA can be converted into NFA . The Turing Machine i.e. TM is more powerful than any other machine

(i) Finite Automata (FA) equivalence:

Finite Automata ≡ PDA with finite Stack ≡ TM with finite tape ≡ TM with unidirectional tape ≡ TM with read only tape

(ii) Pushdown Automata (PDA) equivalence:

PDA ≡ Finite Automata with Stack

(iii) Turing Machine (TM) equivalence:

Turing Machine ≡ PDA with additional Stack ≡ FA with 2 Stacks

The Applications of these Automata are given as follows:

3. Linear Bounded Automata (LBA) –