Scribd
Upload
92 views12 pages

TOC Lab Manual

This practical file presents a series of experiments related to the Theory of Computation for a Bachelor of Technology degree in Computer Science and Engineering. It includes tasks such as constructing DFAs, converting NFAs to DFAs, minimizing DFAs, and designing a Mealy machine. The document is submitted by Muskaan Dhankani and consists of various computational problems with corresponding solutions.

Uploaded by

23rudra30
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
92 views12 pages

TOC Lab Manual

This practical file presents a series of experiments related to the Theory of Computation for a Bachelor of Technology degree in Computer Science and Engineering. It includes tasks such as constructing DFAs, converting NFAs to DFAs, minimizing DFAs, and designing a Mealy machine. The document is submitted by Muskaan Dhankani and consists of various computational problems with corresponding solutions.

Uploaded by

23rudra30
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 12

A

PRACTICAL FILE
ON

Theory of Computation – CS501


SUBMITTED IN PARTIAL FULFILLMENT OF THE REQUIREMENTS FOR THE AWARD OF

THE DEGREE OF

BACHELOR OF TECHNOLOGY
(Computer Science & Engineering)

SUBMITTED TO

RAJIV GANDHI PROUDYOGIKI VISHWAVIDYALAYA, BHOPAL

SUBMITTED TO : SUBMITTED BY:


Mr. Vineet Singh Kushwah Muskaan Dhankani
Asst. Professor, Dept. of CSE 0928CS201057
IPS CTM III Year / V Semester

Department of Computer Science & Engineering

IPS COLLEGE OF TECHNOLOGY AND MANAGEMENT, GWALIOR


DEC-2022

1|Page
INDEX
S.No. Experiments Page Date Sign/
No. Remarks
1. Construct a DFA for the language L={a m b 4
n : m >= 0, n > 0, n is odd}. Design a DFA that
recognizes that language of any number of
a’s followed by any odd number of b’s.
2. Determine the given finite automata is 5
non-deterministic in nature through JFLAP.

3. Convert the given NFA as shown in figure 6


into corresponding DFA.

4. Minimize the given DFA. 7

5. Convert the following DFA into regular 8


grammar.

6. Convert the following DFA into regular 9


expression.

7. Convert a(b+c)*a to DFA. The string must 10


start with an ‘a’ which is followed by a mix
of b’s and c’s repeated in any order.

2|Page
8. Construct a Mealy machine which takes a 11
binary number and replaces the first 1 with
a 0 from every substring starting with 1. For
example, 0001001110 becomes
0000000110.

3|Page
EXPERIMENT NO. 1
Problem : Construct a DFA for the language L={a m b n : m >= 0,
n > 0, n is odd}. Design a DFA that recognizes that language of any
number of a’s followed by any odd number of b’s.

Solution :

4|Page
EXPERIMENT NO. 2
Problem : Determine the given finite automata is non-deterministic
in nature through JFLAP.

Solution : Non-Deterministic states are highlighted

5|Page
EXPERIMENT NO. 3
Problem : Convert the given NFA as shown in figure into
corresponding DFA.

Solution :

6|Page
EXPERIMENT NO. 4
Problem : Minimize the given DFA.

Solution : Minimized DFA is given below :

7|Page
EXPERIMENT NO. 5
Problem : Convert the following DFA into regular grammar.

Solution :

8|Page
EXPERIMENT NO. 6
Problem : Convert the following DFA into regular expression.

Solution :

9|Page
EXPERIMENT NO. 7
Problem : Convert a(b+c)*a to DFA. The string must start with an
‘a’ which is followed by a mix of b’s and c’s repeated in any order.

Solution : The NFA of given regular expression is given below :

The DFA of given regular expression is given below :

10 | P a g e
EXPERIMENT NO. 8
Problem : Construct a Mealy machine which takes a binary
number and replaces the first 1 with a 0 from every substring
starting with 1. For example, 0001001110 becomes 0000000110.

Solution :

11 | P a g e
12 | P a g e

You might also like