Introduction to Automata Theory

The theory of automata is a theoretical branch of computer science and mathematics. 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 analyze the dynamic behavior 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 that 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:

1) Symbols: Symbols are entities or individual objects, which can be any letter, alphabet, or picture.
2) Alphabets: Alphabets are a finite set of symbols. It is denoted by ∑.
3) String: It is a finite collection of symbols from the alphabet. The string is denoted by w.
4) Language: A language is a collection of appropriate strings. A language that is formed over Σ can be Finite or Infinite.

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|.

Let us take an example.

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

Here, L1 is a language. a and b are symbols. These are also the alphabet in the language. {aa,bb,ba,bb} are the strings of the language.