THEORY OF COMPUTATION

SCHOOL OF COMPUTING
DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING



UNIT – I – THEORY OF COMPUTATION – SCSA1302

, SYLLABUS
Introduction - Regular Languages and Regular Expressions - Deterministic Finite Automata -
Non-Deterministic Finite Automata - NFA to DFA Conversion – NFA NULL Construction -
NFA NULL to NFA Conversion - Kleene’s Theorem Part I & II.
1. Introduction
1.1.What is Theory of Computation or Automata Theory?
• Theory of Computation is how efficiently problems can be solved on a model of
computation, using an algorithm.
• It is mainly about what kind of things can you really compute mechanically, how fast
and how much space does it take to complete the task.
• Ex1: To design a machine that accepts all binary strings ends in 0 and reject all other
that does not ends in 0.
11011010 – Accept
• Ex2: To design a machine to accepts all valid ‘C’ codes
Machine will check the binary equivalent of this code and from this binary equivalent
it tells weather it is valid piece of C code or invalid.
Question : Is it possible to design a machine?
Yes – The best example is Compiler.
• Ex3: To design a machine that accepts all valid ‘C’ codes and never goes into infinite.
Question : Is it possible to design a machine?
No




Figure 1.1. Model of a TOC




1

, Table 1.1 Modelling Languages and Language Acceptor




LAYERS AND LEVELS IN THEORY OF COMPUTATION:
• FSM – Finite State Machine – Simplest model of Computation and it has very limited
memory.
Perform low level computation and calculations
• CFL – Context Free Language
Performs some higher level of computation.
• Turing Machine – Much powerful model perform very high level computation designed
by Alan Turing in 1940.
• Undecidable – Problem cannot be solved mechanically is falls under undecidable layer.
1.2 Basic Units of Regular Language:
Alphabets (∑ ) : { a, b} or {0,1}
String( w) : Collection of input alphabets
Language (L) : Collection of Strings
Empty Set :Ø
NULL String : ε or λ
1.3. Finding Language using Conditions:
1. Find L with 0’S and 1’s with odd no. of 1’s
∑ ={ 0,1}

2

, w ={ 1,01,10,100,010, 111,1011……..}
w ={ 1,01,10,100,010, 110 ,111,1011……..} --invalid
L = {w/w consists of odd no. of 1’s}
2. Find L with 0’s and 1’s with even no. of 1’s
∑ ={ 0,1}
w ={Λ ,11,011,101,110,0110, 1010, ……..}
w ={Λ ,11,011,101,100, 110,0110, 1010, …..} --invalid
L = {w/w consists of even no. of 1’s}
3. Find L with a’s and b’s with even no. of a’s
∑ ={ a,b}
w ={Λ ,aa,baa,aba,aab,baab, abba,abab ……..}
w ={Λ ,aa,baa,aaa,aab,baab, abba,abab ……..} --invalid
L = {w/w consists of even no. of a’s}
4. Find L with a’s and b’s with even no of a’s and b’s.
∑ ={ a,b}
w ={Λ ,aa,bb,aabb,abab,baba,bbaa ……..}
L = {w/w consists of even no. of a’s and b’s}
5. Find L with a’s and b’s having a substring aa
∑ ={ a,b}
w ={aa,baa,aab,baab, abaa,aabaa ……..}
L = {w/w consists of a substring aa}
1.4. Regular Language:
• A language is regular if there exits a DFA for that language.
• The language accepted by DFA is RL.
1.5. Regular Expression:
• A Mathematical notation used to describe the regular language.
• This is formed by using 3 Symbols:
(i). [dot operator] – for concatenation
(ii) + [Union operator] –at least 1 occurrence
eg) 1+ = {1,11,111,-------}
(iii) {*} [Closure Operator ] – Zero or more occurrences
eg) 1* = {Λ ,1,11,111,…..}

3