Theory of Computation is a branch of computer science that deals with designing abstract self-propelled computing devices that follow a predetermined sequence of operations automatically.

**Theory of Computation – Basic Terms:**

- Theory of computation is entirely based on symbols. These symbols are generally letters and digits.

Example: 0, 1 are symbols of binary digits

A, B, C, …., Z is symbols of letter alphabet.

- An alphabet is any finite set of symbols.

Example − ∑ = {a, b, c, d} is an alphabet set where ‘a’, ‘b’, ‘c’, and‘d’ are symbols.

∑ = {0, 1} is an alphabet of binary digits set where ‘0’, ‘1’ are symbols.

- To represent alphabet in automata we use Σ (sigma symbol).
- Now there is a rule for checking the validation of alphabets on the basis of which we declare a set of symbols or a symbol valid or invalid.

**Rule: **

If we have used any alphabet then it should not be prefix in the next combination or alphabet.

Σ = {a, b} **✓**** Valid**

Σ = {a, ba, c} **✓**** Valid**

Σ = {a, ab, c} **☓**** Invali****d**

Σ = {0, 10} **✓**** Valid**

Σ = {1, 10, 11} **☓**** Invali****d**

__Power of an alphabet:__

Consider ∑ = {a, b}. The following are the power of an alphabet over input alphabet ∑.

∑ = {null}: zero length string

∑ = {a, b}: set of 1 length string

∑ = {aa, ab}: set of 2 length string

__Algebraic Structure__

A non empty set S is called an algebraic structure with respect to binary operation if (a*b) belongs to S for all (a*b) belongs to S, i.e (*) is closure operation on ‘S’.

**Ex :** S = {1,-1} is algebraic structure under *

As 1*1 = 1, 1*-1 = -1, -1*-1 = 1 all results belongs to S.

But above is not algebraic structure under + as 1+ (-1) = 0 not belongs to S.

**String** is a finite sequence of symbols taken from ∑.

**Ex : ** ‘ cabcad ’ is a valid string on the alphabet set ∑ = {a, b, c, d}

__Set of a String :__

**Definition** – The set of strings, including the empty string, over an alphabet ∑ is denoted by ∑*.
**Examples** − For ∑ = {0, 1} we have set of strings as ∑* = {є, 0, 1, 01, 10, 00, 11, 10101,…}.

and ∑1 = {0, 1} , ∑2 = {00, 01, 10, 11} and so on.

∑* contains an empty string є. The set of non- empty string is denoted by ∑+.