The Basic Terminologies Frequently Used in the Theory of Computation

Symbols: It is the smallest building block, which can be any alphabet, letter, or picture. 

Example:   { a,b,c,0,1,2,3,……}

Alphabet: Alphabets are a finite set of symbols. It is denoted by ∑ (sigma).

Example:

Alphabet set for binary numbers ∑= {0,1}

Alphabet set for decimal numbers ∑= {0, 1,…, 9}

Set of all lower case letters ∑= {a,b,c,….z}

Alphabet set for English language ∑= { A, B, …, Z, a, b, …, z }

 

String: A string or word is a finite set of symbols chosen from some alphabet. A string is generally denoted as w and the length of a string is denoted as |w|. 

Example:

·  ∑ = {0,1}, string that can be generated from this alphabet are {0, 1, 11, 00, 01101 ,….}

·  ∑ = {a, b}, various string that can be generated from this alphabet are: {a, b, aa, ab, ba, bb, aaa, bb, bbb, ba, aba.....}.

 

Empty string: String with zero symbol. An empty string, denoted by e, is a string containing no symbol.

A string with zero occurrences of symbols is known as an empty string or null string. It is denoted by ε (epsilon) or λ (lambda).

Length of a string: The number of symbols in a string w is called the length of a string. It is denoted by |w|.

Example:

∑ = {0,1}

w = 01011      |w|= |01011|=5

If w=ε ,  then |w|=0       

 

Powers of an Alphabet: ∑k is the set of strings of length k chosen from ∑.

∑⁰={ ε}

∑ ¹={0,1}

∑ ²={00,01,10,11}

∑ ³={000,001,010,011,100,101,110,111}

………………..

 Set of all strings over an alphabet ∑,

 ∑*=∑⁰U∑ ¹U∑ ²U……

{0,1}*={ ε,0,1,00,01,10,11,…….}

 

Concatenation of the strings:

x=110         y=001

xy=110001

yx=001110

Language: A language is a set of strings or words chosen from some ∑* or we can say -A language is a subset of ∑* . A language that can be formed over ‘ Σ ‘ can be Finite or Infinite. It is denoted by L.

 

·   Φ denotes empty language.

·   { ε} language consist of  empty string.

 

Example:

Set of binary numbers whose value is a prime
L={10,11,101,111,….}

Language of all strings consisting of n 0’s followed by n 1’s, for some n>=0:
L={ ε,01,0011,000111,….}

Set of strings of 0’s and 1’s with equal number of each
L={ ε,01,10,0011,0101,1010,…}

Example of Finite Language:
L1 = { set of string of length 2 }
L1 = { aa,ab,ba,bb }

Example of Infinite Language:
L1 = { set of all strings starts with 'a' }
L1 = { a,aa,aaa,ab,aab,aba,abb ....... }