Computer Science Engineering (CSE)  >  Theory of Computation  >  Introduction: Theory of Computation

Introduction: Theory of Computation Notes | Study Theory of Computation - Computer Science Engineering (CSE)

Document Description: Introduction: Theory of Computation for Computer Science Engineering (CSE) 2022 is part of Theory of Computation preparation. The notes and questions for Introduction: Theory of Computation have been prepared according to the Computer Science Engineering (CSE) exam syllabus. Information about Introduction: Theory of Computation covers topics like Definition - Theory of Computation, Basics of Formal Language Theory and Introduction: Theory of Computation Example, for Computer Science Engineering (CSE) 2022 Exam. Find important definitions, questions, notes, meanings, examples, exercises and tests below for Introduction: Theory of Computation.

Introduction of Introduction: Theory of Computation in English is available as part of our Theory of Computation for Computer Science Engineering (CSE) & Introduction: Theory of Computation in Hindi for Theory of Computation course. Download more important topics related with notes, lectures and mock test series for Computer Science Engineering (CSE) Exam by signing up for free. Computer Science Engineering (CSE): Introduction: Theory of Computation Notes | Study Theory of Computation - Computer Science Engineering (CSE)
Table of contents
Definition - Theory of Computation
Basics of Formal Language Theory
1 Crore+ students have signed up on EduRev. Have you?

Definition - Theory of Computation

Automata theory (also known as Theory Of Computation) is a theoretical branch of Computer Science and Mathematics, which mainly deals with the logic of computation with respect to simple machines, referred to as automata.
Theory Of ComputationTheory Of Computation

Some more points regarding the theory of computation: 

  • Automata* enables the scientists to understand how machines compute the functions and solve problems. 
  • The main motivation behind developing Automata Theory was to develop methods to describe and analyse the dynamic behavior of discrete systems.
  • The field is divided into three major branches: automata theory, computability theory and computational complexity theory. 
  • In order to perform a rigorous study of computation, computer scientists work with a mathematical abstraction of computers called a model of computation. There are several models in use, but the most commonly examined is the Turing machine
  • Automata is originated from the word “Automaton” which is closely related to “Automation”.
  • This automaton consists of:
    1. states (represented in the figure by circles),
    2. transitions (represented by arrows). 
  • As the automaton sees a symbol of input, it makes a transition (or jump) to another state, according to its transition function (which takes the current state and the recent symbol as its inputs). Uses of Automata: compiler design and parsing.
    Introduction: Theory of Computation Notes | Study Theory of Computation - Computer Science Engineering (CSE) 

Question for Introduction: Theory of Computation
Try yourself:Automata word has originated from which word?
View Solution

Basics of Formal Language Theory

Our view of languages is that a language is a set of strings. In turn, a string is a finite sequence of letters from some alphabet. These concepts are defined rigorously as follows. 

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

Introduction: Theory of Computation Notes | Study Theory of Computation - Computer Science Engineering (CSE)

2. Alphabets (Σ): Alphabets are set of symbols, which are always finite. 

Introduction: Theory of Computation Notes | Study Theory of Computation - Computer Science Engineering (CSE)

3. String: String is a finite sequence of symbols from some alphabet. String is generally denoted as w and length of a string is denoted as |w|.
Empty string is the string with zero occurrence of symbols, represented as ε.
Number of Strings (of length 2) that can be generated over the alphabet {a, b} -
Introduction: Theory of Computation Notes | Study Theory of Computation - Computer Science Engineering (CSE)
Length of String |w| = 2
Number of Strings = 4

Conclusion:
For alphabet {a, b} with length n, number of strings can be generated = 2n.
Note: If the number of Σ’s is represented by |Σ|, then number of strings of length n, possible over Σ is |Σ|n. 

4. Language: A language is a set of strings, chosen from some Σ* or we can say- A language is a subset of Σ* . A language which can be formed over ‘ Σ ‘ can be Finite or Infinite. 

Introduction: Theory of Computation Notes | Study Theory of Computation - Computer Science Engineering (CSE)

5. Powers of ‘Σ‘:
Say Σ = {a,b} then
Σ0 = Set of all strings over Σ of length 0. {ε}
Σ1 = Set of all strings over Σ of length 1. {a, b}
Σ2 = Set of all strings over Σ of length 2. {aa, ab, ba, bb}
i.e. |Σ2|= 4 and Similarly, |Σ3| = 8
Σ* is a Universal Set.
Σ* = Σ0 U ΣU Σ2 ..........
= {ε} U {a, b} U {aa, ab, ba, bb}
= .............   //infinite language

6. Convention:

Capital letters A, B, C, L, etc. with or without subscripts are normally used to denote languages.

 

The document Introduction: Theory of Computation Notes | Study Theory of Computation - Computer Science Engineering (CSE) is a part of the Computer Science Engineering (CSE) Course Theory of Computation.
All you need of Computer Science Engineering (CSE) at this link: Computer Science Engineering (CSE)
18 videos|56 docs|41 tests
Download as PDF

Download free EduRev App

Track your progress, build streaks, highlight & save important lessons and more!

Related Searches

Sample Paper

,

practice quizzes

,

Free

,

Introduction: Theory of Computation Notes | Study Theory of Computation - Computer Science Engineering (CSE)

,

Objective type Questions

,

mock tests for examination

,

study material

,

Exam

,

past year papers

,

shortcuts and tricks

,

Introduction: Theory of Computation Notes | Study Theory of Computation - Computer Science Engineering (CSE)

,

pdf

,

Extra Questions

,

Summary

,

Semester Notes

,

Introduction: Theory of Computation Notes | Study Theory of Computation - Computer Science Engineering (CSE)

,

ppt

,

Important questions

,

video lectures

,

MCQs

,

Viva Questions

,

Previous Year Questions with Solutions

;