# Introduction to Theory of Computation

By BYJU'S Exam Prep

Updated on: September 25th, 2023

**Study Notes on Introduction of Theory of Computation**– In this subject, our main motive is to prove the statement :

“Everything which has a logic can be simulated on a machine “

or, in other words, a problem that can be solved using an algorithm can also be solved by the computer.

To understand this subject we will consider some machines like Finite Automata, Push Down Automata and Turing Machines. Using these models, we will solve all those problems which have an algorithm behind them. For ex: all mathematical functions and logic. Multiplying two numbers have logic behind them, so we can perform it using the computer.

Let suppose, we have 100 different numbers on a screen, and you have to choose one number in your mind. The computer is unable to guess that number because this problem doesn’t have any logic behind it as you can choose any number you want.

Table of content

**Study Notes on Introduction of Theory of Computation**– In this subject, our main motive is to prove the statement :

Everything which has a logic can be simulated on a machine

or, in other words, a problem that can be solved using an algorithm can also be solved by the computer.

To understand this subject we will consider some machines like Finite Automata, Push Down Automata and Turing Machines. Using these models, we will solve all those problems which have an algorithm behind them. For ex: all mathematical functions and logic. Multiplying two numbers have logic behind them, so we can perform it using the computer.

Let suppose, we have 100 different numbers on a screen, and you have to choose one number in your mind. The computer is unable to guess that number because this problem doesn’t have any logic behind it as you can choose any number you want.

This subject is divided into 3 main parts :

- Automata and languages
- Computability theory
- Time complexity

**Automata: **Study of abstract computing devices or machines.

**Symbol: **It is an abstract entity (letters and digits)

- Example: 0,1

**Alphabet (∑):** An alphabet may be defined as a finite, non-empty set of symbols.

- Example: Binary alphabet ∑ = {0, 1}

**String:** It is a sequence of symbols.

- Example: 0101 is a string

**Finite String:** Finite String is said to be a finite sequence of symbols.

- Example: 010 is a finite string that has a length of 3.

**Infinite String: **Infinite sequence of symbols.

- Example: 011111… is an infinite string that has infinite length. (infinite strings are not used in any formal language)

**Language:** A language is defined as a collection of sentences of finite length and all are constructed from a finite alphabet of symbols.

- Example: L = {00, 010, 00000, 110000} is a language over input alphabet ∑ = {0, 1}

**Formal Language:** Formal language is defined as a language that is restricted to be designed from a set of finite alphabets.

Example:

- Set of all strings where each string starts with 1 over a binary alphabet.
- L={1, 10, 11, …} over 0’s and 1’s.

**Empty String (Λ or ε or λ):** If the length of the string is zero, so such string will be known as a void string or an empty string.

**Kleene Closure**

- If ∑ is the Alphabet, then there is a language in which any string of letters ∑ 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**. - If ∑ = {a, b}, then ∑
^{*}= {ε, a, b, a, ab, bb,….}

∑^{*} = ∑^{0 }**∪** ∑^{1 }**∪** ∑^{2 }**∪** …

∑^{*} = ∑^{+ }**∪** {ε}

**Positive Closure:**

- The’ +’ (plus operation) is sometimes called
**positive Closure.** - If ∑ = {a}, then ∑
^{+}= {a, aa, aaa, …} = the set of nonempty strings from ∑

∑^{+ }= ∑^{*} **–** {ε}

**Concatenation of two strings:**

- 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
**x.y**, it is the same as**xy**.

**Substring of a string:**

- A string v is a substring of a string ω if and only if there are some strings x and y such that ω = xvy.

**Suffix of a string:**

- If ω = xv for some string x, then v is suffix of ω.

**Prefix of a string:**

- If ω = vy for some string y, then v is a prefix of ω.

**Reversal of a string:**

- Given a string ω, its reversal denoted by ω
^{R}is the string spelt backwards.

**Grammar:**

- It enumerates strings of the language. It is a finite set of rules defining a language.
- A grammar is defined as 4-tuples (V
_{N}, ∑, P, S), - where, V
_{N}is a finite non-empty set of non-terminals, ∑ is a finite non-empty set of input terminals, P is a finite set of production rules, and S is the start symbol.

**Chomsky Hierarchy**

The Chomsky hierarchy consists of the following four types of classes.

**Type 0 Grammar **(Unrestricted Grammar):

- These are unrestricted grammars which include all formal grammars.
- These grammars generate exactly all languages that can be recognized by a Turing machine.
- Rules are of the form α → β,
- where, α and β are arbitrary sequences of terminals and non-terminals and α ≠ ∧ (null).

**Type 1 Grammar **(Context Sensitive Grammar):

- Languages defined by type-1 grammars are accepted by linear bounded automata.
- Rules are of the form X → Y, where, X, Y ∈(V
_{N}∪ ∑)^{*}, and Length of X is less than or equal to the length of Y.

**Type 2 Grammar **(Context-free Grammar):

- Languages defined by type-2 grammars are accepted by push-down automata.
- Rules are of the form A → α, where, A ∈V
_{N }, and α∈(V_{N}∪ ∑)^{*}

**Type 3 Grammar **(Regular Grammar):

- Languages defined by type-3 grammars are accepted by finite-state automata.
- Regular grammar can follow either right linear or left linear.
- Right linear rules are of the form: A → α | αB where, A, B ∈ V
_{N}and α∈∑*. - Left linear rules are of the form: A → α | Bα where, A, B ∈ V
_{N}and α∈∑*.

**Type-0 Class is also called as:**

- Unrestricted Grammars
- Recursively Enumerable Languages
- Turing Machine

**Type-1 Class is also called as:**

- Context-Sensitive Grammars
- Context-Sensitive Languages
- Linear Bound Automata

**Type-2 Class is also called as:**

- Context-Free Grammars
- Context-Free Languages
- Push Down Automata

**Type-3 Class is also called as:**

- Regular Grammars
- Regular Languages
- Finite Automata

**Finite Automata (FA): **

- Machines with a fixed amount of unstructured memory accept regular languages.
- Applications of FA: useful for modelling chips, communication protocols, adventure games, some control systems, lexical analysis of compiler design, etc.

**Pushdown Automata (PDA): **

- Finite Automata with unbounded structured memory in the form of a pushdown stack accepts context-free languages.
- Application of PDA: useful for modelling parsing, compilers, postfix evaluations, etc.

**Turing Machine (TM):**

- Finite Automata with unbounded tape accepts or enumerates recursively enumerable languages.
- Equivalent to RAMs, and various programming languages models.
- Applications of TM: Model for general sequential computation (real computer).

You can follow the detailed champion study plan for GATE CS 2022 from the following link:

**Detailed GATE CSE 2022 Champion Study Plan**

Candidates can also practice 110+ Mock tests for exams like GATE, ISRO, DRDO, BARC, NIELIT, etc. with the BYJU’S Exam Prep Test Series, check the following link to avail it:

## Click Here to Avail GATE CSE Test Series! (100+ Mock Tests)

Get unlimited access to 21+ structured Live Courses all 112+ mock tests with the Online Classroom Program for GATE CS & PSU Exams:

## Click here to avail Online Classroom Program for Computer Science Engineering

**Thanks**

**#DreamStriveSucceed**