Theory of automata is a theoretical branch of computer science and mathematical. It is the study of abstract machines and the computation problems that can be solved using these machines. The abstract machine is called the automata. The main motivation behind developing the automata theory was to develop methods to describe and analyse the dynamic behaviour of discrete systems.

This automaton consists of states and transitions. The **State** is represented by **circles**, and the **Transitions** is represented by **arrows**.

Automata is the kind of machine which takes some string as input and this input goes through a finite number of states and may enter in the final state.

There are the basic terminologies that are important and frequently used in automata:

### Symbols:

Symbols are an entity or individual objects, which can be any letter, alphabet or any picture.

### Example:

1, a, b, #

### Alphabets:

Alphabets are a finite set of symbols. It is denoted by ∑.

### Examples:

- ∑ = {a, b}
- ∑ = {A, B, C, D}
- ∑ = {0, 1, 2}
- ∑ = {0, 1, ….., 5]
- ∑ = {#, β, Δ}

### String:

It is a finite collection of symbols from the alphabet. The string is denoted by w.

### Example 1:

If ∑ = {a, b}, various string that can be generated from ∑ are {ab, aa, aaa, bb, bbb, ba, aba…..}.

- A string with zero occurrences of symbols is known as an empty string. It is represented by ε.
- The number of symbols in a string w is called the length of a string. It is denoted by |w|.

### Example 2:

- w = 010
- Number of Sting |w| = 3

### Language:

A language is a collection of appropriate string. A language which is formed over Σ can be **Finite** or **Infinite**.

### Example: 1

L1 = {Set of string of length 2} = {aa, bb, ba, bb}Finite Language

### Example: 2

L2 = {Set of all strings starts with 'a'} = {a, aa, aaa, abb, abbb, ababb}Infinite Language

**Theory of Automata****Finite Automata****Transition Diagram****Transition Table****DFA (Deterministic finite automata)****Examples of DFA****NFA (Non-Deterministic finite automata)****Examples of NFA****Eliminating ε Transitions****Conversion from NFA to DFA****Conversion from NFA with ε to DFA****Minimization of DFA****Regular Expression****Examples of Regular Expression****Moore Machine****Mealy Machine****Context Free Grammar****Simplification of CFG****Chomsky’s Normal Form (CNF)****Greibach Normal Form (GNF)****Pushdown Automata(PDA)****Non-deterministic Pushdown Automata****Turing Machine****Examples of TM**