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