SUSHILA DEVI BANSAL COLLEGE OF TECHNOLOGY, INDORE

Department of Computer Science & Engineering

Academic Session:-Jul-Dec 2024
Lab Plan
Course: B.Tech Year: 3rd Sem: 5th Section:
Subject Code : CS501 Subject Name: Theory of Computation
Name of Faculty: Shraddha Kumar Total No of Labs Required:

No. of Students Present Reference/ Text Book

Lab No. Topic Scheduled Date Completition Date COs HoD Weekly Sign
(out of 78 ) Web Reference

1 Introduction of JFLAP CO1 T1

Design a Program for creating machine that accepts three

2 CO1 T1
consecutive one.
Design a Program for creating machine that accepts the string
3 CO1 T1
always ending with 101.

4 Design a Program for mod-3 Machine. CO1 T1

Design a program for accepting decimal number divisible by

5 CO1 T1
2.
Design a program for creating a machine which accepts string
6 CO1 T1
having equal no. of 1’s and 0’s.
Design a program for creating a machine which count number
7 CO1 T1
of 1’s and 0’s in a given string.
Design a Program to find 2’s complement of a given binary
8 CO2 T1
number.

9 Design a Program to convert NDFA to DFA. CO2 T1

Design a Program to create PDA machine that accept { a2nbn |

10 CO4 T2
n>=1}

Design a PDA to accept wcwR where w is any string and wR

11 CO4 T2
is reverse of that string and c is a Special symbol

12 Design a Turing machine that’s accepts anbncn the following CO5 T2

language where n>0.

Course Outcomes (COs)

CO1 List the examples of automata machines and state the basic concept of FAs.
CO2 Classify DFA and NDFA, and explain operations on DFA and NDFA.
CO3 Dicriminate types of Grammars and solve various problems such as simplification and conversion of Grammars.
CO4 Design and create Push Down Automata. Translate PDA to Grammar and vice versa.
CO5 Design and create turing Machine and assess various types of real world problems.

Text (T)/
Reference
S. No. Title of the Text Book/ Reference Book/ Web links Author Edition/ Volume
(R)/ Web
(W)
1 Theory of Computation Chandrasekhar & Mishra, PHI. II T1
2 Element of the Theory Computation Lewis & Christors, Pearson III T2
3 Formal Languages & Automata Peter Linz, Narosa IV R1
4 Introduction to Computing Theory Daniel I-A Cohen, Wiley I R2
5 Introduction to Automata Theory Language & Computation Hopcroft& Ullman, Narosa Publicati I R3
6 http://turingmaschine.klickagent.ch/einband/?lang=en#4_!_ W1
7 https://web.cs.hacettepe.edu.tr/~ilyas/Courses/BIL405/lec03_RegExpRegLang.pdf W2

Name & Signature of Faculty………………………………… Signature of HOD……………………….

 SUSHILA DEVI BANSAL COLLEGE OF TECHNOLOGY, INDORE
Department of Computer Science & Engineering
Academic Session:-Jul-Dec 2024
Lab Plan
Course: B.Tech Year: 3rd
Subject Code : CS501 Subject Name: Theory of Comp
Name of Faculty: Manisha Kadam Total No of Labs Required:

Date of Experiment
Lab No. Topic

1 Introduction of JFLAP 6/9/2024

2 Design a Program for creating machine that accepts three consecutive one. 13/09/24

Design a Program for creating machine that accepts the string always ending
3 20/9/24
with 101.

4 Design a Program for mod-3 Machine. 27/09/24

5 Design a program for accepting decimal number divisible by 2. 5/10/2024

Design a program for creating a machine which accepts string having equal
6 19/10/24
no. of 1’s and 0’s.
Design a program for creating a machine which count number of 1’s and 0’s
7 26/10/24
in a given string.

8 Design a Program to find 2’s complement of a given binary number. 8/11/2024

9 Design a Program to convert NDFA to DFA. 15/11/24

10 Design a Program to create PDA machine that accept { a2nbn | n>=1} 22/11/24

Design a PDA to accept wcwR where w is any string and wR is reverse of that
11 29/11/24
string and c is a Special symbol

12 Design a Turing machine that’s accepts anbncn the following language 6/12/2024
where n>0.

Course Outcomes (COs)

 CO1
List the examples of automata machines and state the basic concept of FAs.

CO2
Classify DFA and NDFA, and explain operations on DFA and NDFA.

CO3
Dicriminate types of Grammars and solve various problems such as simplification and conversion of Grammars.

CO4
Design and create Push Down Automata. Translate PDA to Grammar and vice versa.

CO5
Design and create turing Machine and assess various types of real world problems.

S. No. Title of the Text Book/ Reference Book/ Web links

1
Theory of Computation

2
Element of the Theory Computation

3
Formal Languages & Automata

4
Introduction to Computing Theory

5
Introduction to Automata Theory Language & Computation

6
http://turingmaschine.klickagent.ch/einband/?lang=en#4_!_
7
https://web.cs.hacettepe.edu.tr/~ilyas/Courses/BIL405/lec03_RegExpRegLang.pdf

Name & Signature of Faculty…………………………………

GY, INDORE
ng

Sem: 5th Section: B

me: Theory of Computation
Labs Required:

Completition Date Remark

Os)
ersion of Grammars.

Text (T)/
Edition/ Referenc
b links
Volume e (R)/
Web (W)
T1
II

III T2

IV R1

I R2

I R3

W1

W2