# Introduction of Theory of Computation

**Alphabets:-**

An alphabet is a set of finite , non-empty set of symbol we use the symbol ∑ for an alphabet.

eg:

∑ ={0,1} is the binary alphabet.

**String:-**

A string (or sometimes word) is a finite sequence of symbols choose from some alphabets

eg:-

10010 is a string from the binary alphabet ∑={0,1}

**Empty String:-**

Empty string is the string with zero occurrences of the symbols denoted by ∑ .Empty string is also called as "Null String".

**Length of String:-**

The no. of symbols in the string notation for length of string w is |w| -----(carnality)

|a11|=3

|∑|=0

The number of symbol in the sequence of given string is called "length of string".

**eg:-**

|abb|=3,for the string abb over ∑=(a,b)

**Substring of a String:-**Any sequence of zero or more consecutive symbols of the give string over an alphabet is called a "substring of string".

**Example:-**For string abb over ∑={a,b},the possible substring are

£,a,b,ab,bb and abb.

**Prefix of a String:-**Any substring with the sequence of beginning symbols of a given string is called a "Prefix".

**Example:-**For string "abb" ,the possible prefixes of abb are;

£,a,ab,abb.

**Suffix of a String:-**Any substring with the sequence of trailing(ending) symbols of a given string is called a "Suffix".

**Example:-**For string "abb" ,the possible suffixed are;

£,b,bb,abb.

**Language:-**A set of string over the given alphabet ∑ is called a "language" (or collection of string).

**Example:-**Let ∑={a,b}.Then Language L-{ab,aab}.

## No comments