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={0,1}

2={00,01,10,11}

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

………………..

 Set of all strings over an alphabet ∑,

 ∑*=0U∑ 1U∑ 2U……

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

2 thoughts on “The basic terminologies frequently used in the Theory of Computation”

  1. Thanks for the blog post, this will be a great help for us.
    Please continue the great work, hope more students find help with the blogs that you have come up with.
    This is a great help for those who look up for their subject related to Computer Science,
    to find all the related documents and examples in a single place / link.

    Reply

Leave a Comment