**Introduction **

Theoretical Computer Science is a branch of computer science and mathematics in which we study mathematical aspects of computer science.

One of the branches of theoretical computer science is the ‘Theory of Computation’, which deals with what are the problems that can be solved using an algorithm on a model of computation and also up to what extent and with what accuracy these problems can be solved.

This field of ‘Theory of Computation’ is divided into three major branches and ‘Automata Theory’ is one of them.

Automata theory is the branch of theoretical computer science that focuses on the study of computational problems that can be solved by machines called automata.

Automata takes strings as inputs and this input goes through predetermined operations called states. Automata are used to study how the machines compute and solve the problems.

Now, let’s learn about the basic terminologies that are used in automata theory.

Also see, __Turing Machine in TOC____.__

You can also read about __Greibach Normal Form__ here.

**Basic Terminologies of Automata Theory**

In this section, we will discuss the basic terminologies that are frequently used in Automata Theory.

The following terminologies are important in Automata Theory:

**1. Symbols**

Symbols are individual elements which are the basic building blocks, and can be any picture, letter or alphabet. Examples: 0, 1, a, b, .. etc.

**2. Alphabets**

Alphabets are a set of symbols denoted by ∑.

Example:

∑ = {A, B, C} is an alphabet set where ‘A’, ‘B’, and ‘C’ are symbols

∑ = {1, 2, 3} is an alphabet set where ‘1’, ‘2’, and ‘3’ are symbols

**3. String**

String is a finite sequence of symbols from any alphabet. It is generally denoted by ‘w’ and the length of the string is denoted by |w|.

Example:

For an alphabet ∑ = {A, B, C}, the following strings can be generated through this set -

{“AAA”, “A”, “AA”, “AB”, ……….}

** Note:** An empty string i.e. the string with zero occurrences of symbols is represented by ε.

**4. Language**

A language is a set of strings selected from all the strings that can be generated from a given alphabet set. It can be finite or infinite.

Suppose an alphabet ∑ = {a, b, c}

Set of strings from this alphabet = {“a”, “aa”, “aaa”, “b”, “bb”, “ab”, ………..}

An example of finite language is

Language1 = {set of strings of length 1}

= {‘a’, ‘b’, ‘c’}

An example of infinite language is

Language2 = {set of strings containing only ‘a’}

= {‘a’, “aa”, “aaa”, “aaaa” ………}

**5. Kleene star**

Keelene star is an unary operator on a set of strings that gives an infinite set of all possible strings with all possible lengths including zero-length string (ε). It is denoted by ∑* .

Suppose ∑ = {a, b, c}

Then, ∑* = {ε, a, b, c, aa, bb, ……..}

**6. Kleene Closure**

Keelene Closure is an unary operator on a set of strings that gives an infinite set of all possible strings with all possible lengths excluding zero-length strings (ε). It is denoted by ∑^{+} .

Suppose ∑ = {a, b, c}

Then, ∑^{+} = {ε, a, b, c, aa, bb, ……..}

Also See, __Moore Machine__

Also read, __Arden's theorem__