Basics of Theory of Computation Tutorial Study Notes updated [year]

1. Theory of Computation

   

 Basics of Theory of Computation

•           Computation is defined as any type of calculation. It is also defined as use of computer technology information processing. The theory of computation is the branch that deals with whether and how efficiently problems can be solved on a model of computation, using an algorithm.

Basic Definitions

Symbol          A symbol is an abstract entity i.e., letters and digits

String            A String is a finite sequence of symbols.

Alphabet      An alphabet is a finite set of symbols, usually denoted by Σ.

Language    A formal language is a set of strings of symbols from some alphabet.

Key Points

• Generally a, b, c, ……used to denote symbols. Alphabets will represent the observable events of an automata.
• Generally w, x, y, z used to denote words. A word will represent the behavior of an automation.

Kleene Closure

It Σ is the set of alphabets, then there is a language is which any string of letters from Σ is a word, even the null string. We call this Language closure of the alphabet. It is denoted by * (asterisk) after the name of the alphabet is Σ^*. This notation is also known as the Kleene Star.

e.g.,                            if Σ = {a}, then

                                    Σ^* = {Λ, a, aa, aaa, …}

 Where, Λ represents null String.

if                                  if Σ = {a, b}, then

                                    Σ^* = {Λ, a, b, aa, ab, aaa, …}

Key Points

• By using Kleene Star operation, we can make an infinite language of strings of letters of of alphabet.
• The words in increasing order of length called lexicographic order.

 Positive Closure

The ‘+’ (Plus Operation) is sometimes called positive closure. A+ (Plus) closure never contain null value.

If                     Σ = {a}, then Σ^* = {a, aa, aaa, …}

  Note :If S is the set of strings, then S^* is the language S^* without the word Λ.

Operations Over Words In Σ^*

• Concatenation if x, y ϵ Σ^*, then x concatenated with y is the word formed by the symbols of x followed by the symbols of y. This is denoted by xy.
• Substring A string v is a substring of a string ω if and only if there are strings x and y such that ω = xvy.
• Suffix if ω = xv for some string x, then v is suffix of ω.
• Prefix if ω = vy for some string y, then v is suffix of ω.
• Reversal Give a string ω, its reversal denoted by ω^R is the string speeled backwards.

e.g.,    (abcd)^R = dcba

Alphabet Ʃ^*

Ʃ^* It is the set of all words for a given alphabet Ʃ. This can be described inductively in at least two different ways

• Basic case The empty word ^ is the Ʃ^* (notation : ^ ϵ Ʃ^* )

Inductive Step If a ϵ Ʃ and x ϵ Ʃ^* ,then ax ϵ Ʃ^*

                                    And also xa ϵ Ʃ^*  

• Null set The language that has no words and can be represented by ɸ.

 

Theory of computation (TOC) is a branch of Computer Science that is concerned with how problems can be solved using algorithms and how efficiently they can be solved. Real-world computers perform computations that by nature run like mathematical models to solve problems in systematic ways.  Real-world computers perform computations that by nature run like mathematical models to solve problems in systematic ways. The essence of the theory of computation is to help develop mathematical and logical models that run efficiently and to the point of halting. Since all machines that implement logic apply TOC, studying TOC gives learners an insight into computer hardware and software limitations.

---

Basics of Theory of Computation Tutorial Study Notes with Examples

Follow Us on Social Platforms to get Updated : twiter,  facebook, Google Plus

The Complete Guide of Computer Science : Click here

Learn JavaScript in Hindi:  Click here