Introduction to Automata

Automata is the mathematical model or machine that helps to solve the problem. The problem is that whether the string is the part of the language or not. Automata is the many or multiple of automaton. It means that it works automatically or self-acting. Automatic machine is a machine that take input from the user then it performs all steps itself.

In Introduction to Automata, learn the basics of Automata Theory, its main types, key concepts and how Automata work with formal languages.

There are four most important types of automata are as follow.

• FA (Finite Automata)
• PDA (Pushdown Automata)
• LBA (Linear Bounded Automata)
• TM (Turing Machine)

1. Finite Automata (FA)

Finite Automata (FA) is also called Finite Automata Machine (FAM). Finite Automata is used for defining languages with the help of the diagram. It is also used in graphical method that consist of five method. Finite means limited, in easy words we can say that everything has a limit and Automata means that is the many or multiple of automaton i.e. automatic, self controlled machine. Finite Automata are mostly used to make a diagram. Finite Automata (FA) are also used to represent Regular Grammar (RG). It accept only regular language. It is less powerful than PDA,LBA and TM. It is called a Finite Automaton because it has a Finite Number of States, Input Symbols, Transitions or Movement, one Initial State and one or more Final State. Five tuples of Finite Automata are as follow.

FA = (q, q₀, f, Σ , δ)

Hare the explanation of five tuples are given.

• q show the Number of States.
• q₀ show the Initial State.
• F show the Final State.
• Σ show the Letters in the Alphabet.
• δ show the Transitions or Movements.

Five Tuple Table of Finite Automata

Hare the table of Finite Automata are given or shown.

Example

L = {aⁿ ∣ n ≥ 1}

Types of Finite Automata

Two types of Finite Automata are as follow.

• Deterministic Finite Automata (DFA)
• Non-Deterministic Finite Automata (NFA)

i. Deterministic Finite Automata (DFA)

DFA stand for Deterministic Finite Automata. However the main difference of DFA and NFA, the DFA has only one possible next state and NFA have more than one possible next state. We can defined the DFA for using the five tuples. Every tuple has its own specific purpose. Five tuples are as follow.

DFA = (q,q₀,f,Σ,δ)

Hare the explanation of five tuples are given.

• q show the Number of States.
• q₀ show the Initial State.
• F show the Final State.
• Σ show the Letters in the Alphabet.
• δ show the Transitions or Movements.

Rule: δ: q×Σ→q

Example

Explanation

In Deterministic Finite Automata (DFA) example show that q₀ is the initial state, q₁, q₂, q₃ is the state, q₄ is the final state and q₅ is known as dead state. This example show that DFA has only one possible next state. In easy words we can say that the strings start with a and end with the e. So this example explain the step by step the concept of DFA.

ii. Non-Deterministic Finite Automata (NFA)

NFA stand for Non-Deterministic Finite Automata. However the main difference of NFA and DFA, NFA have more than one possible next state and the DFA has only one possible next state. We can defined the NFA for using the five tuples. Every tuple has its own specific purpose. Five tuples are as follow.

NFA = (q, q₀, f, Σ , δ)

Hare the explanation of five tuples are given.

• q show the Number of States.
• q₀ show the Initial State.
• F show the Final State.
• Σ show the Letters in the Alphabet.
• δ show the Transitions or Movements.

Rule: q×Σ→2ᑫ

Example

Explanation

In Non-Deterministic Finite Automata (NFA) example show that q₀ is the initial state, q₁ is the state,  q₂ is the final state and q₃ is known as dead state. This example show that NFA have more than one possible next state. In easy words we can say that the strings start with 0 and end with 1. So this example explain the step by step the concept of NFA.

2.Pushdown Automata (PDA)

PDA stand for Pushdown Automata. It is called a Pushdown Automata because it has a Finite Number of States, Input Symbols, Transitions function or Movement, Initial State, Initial Stack Symbol, Stack Alphabet and Final State. PDA same as a Finite Automata but two additional things add in PDA such as Initial Stack Symbol and Stack Alphabet. PDA is the second most important type of Automata. Pushdown Automata is used to represent a Context-Free Grammar (CFG) and accept only CFG. It is more powerful than FA and less powerful than LBA and TM. We can easily define PDA by using seven tuples. These seven tuples are as follow.

PDA = (q,Σ,δ,q₀,z₀,Γ,F)

Hare the explanation of seven tuples are given.

• q show the Number of States.
• Σ show the Letters in the Alphabet.
• δ show the Transitions or Movements.
• q₀ show the Initial State.
• z₀ show the Initial Stack Symbol.
• Γ Stack Alphabet.
• F Show the Final State.

Example

L = { aⁿbⁿ | n ≥ 1 }

General Structure

Explanation 

In easy words we can explain the general structure of Pushdown Automata (PDA). A Pushdown Automata uses a single stack to keep information while processing the input.

Types of PDA

• Deterministic Pushdown Automata (DPDA)
• Non-Deterministic Pushdown Automata (NPDA)

i. Deterministic Pushdown Automata (DPDA)

DPDA stand for Deterministic Pushdown Automata. DPDA is less powerful than NPDA. The power of DPDA and NPDA can not the same because DPDA can make only one choice. One choice means only one possible move.

ii. Non-Deterministic Pushdown Automata (NPDA)

NPDA stand for Non-Deterministic Pushdown Automata. NPDA is more powerful than DPDA. The power of NPDA and DPDA can not the same because NPDA can make multiple choices. Multiple choices means more than one possible move.

3.Linear Bounded Automata (LBA)

LBA stand for Linear Bounded Automata. LBA is actually a Turing machine with a limited size tape. LBA is more powerful than Finite Automata (FA) and (PDA). LBA is less powerful than Turing Machine (TM). LBA accept only Case-Sensitive Language (CSL). It is called a Linear Bounded Automata because it has a Finite Number of States, Input Alphabet, Transitions function or Movement, Initial State, Blank Symbol, Tape Alphabet and Final State.

LBA = (q,Σ,δ,q₀,B,Γ,F)

Hare the explanation of seven tuples are given.

• q show the Number of States.
• Σ show the Letters in the Alphabet.
• δ show the Transitions or Movements.
• q₀ show the Initial State.
• B show the Blank Symbol.
• Γ Show the Tape Alphabet.
• F Show the Final State

Example

L = {aⁿbⁿcⁿ ∣ n ≥ 1}

General Structure

Explanation 

In easy words we can explain the general structure of Linear Bounded Automata (LBA). In this general structure show that the tape size is limited according to the input length.

4.Turing Machine (TM)

TM stand for Turing Machine. A Turing Machine (TM) is a mathematical model of computation. It is used to solve the problems that require more memory and more comparisons than a Finite Automaton (FA) or a Pushdown Automaton (PDA). Turing Machine (TM) accept Recursively Enumerable (RE) and Recursive Language (REC). Turing Machine (TM) is more powerful than Finite Automata (FA), Pushdown Automata (PDA) and Linear Bounded Automata (LBA). It is called a Turing Machine (TM) because it has a Finite Number of States, Input Alphabet, Transitions function or Movement, Initial State, Blank Symbol, Tape Alphabet and Final State.

TM = (q,Σ,δ,q₀,B,Γ,F)

Hare the explanation of seven tuples are given.

• q show the Number of States.
• Σ show the Letters in the Alphabet.
• δ show the Transitions or Movements.
• q₀ show the Initial State.
• B show the Blank Symbol.
• Γ Show the Tape Alphabet.
• F Show the Final State

Example

Γ = {0, 1, X, Y, B}

TM Diagram (General Structure)

Explanation 

In easy words we can explain the general structure of Turing Machine (TM). In this general structure show that the TM uses an unlimited tape to read. It is the most powerful automaton and can solve very complex computational problems.

Note: FA < PDA < LBM < TM