[go: up one dir, main page]
Scribd
Upload
91 views30 pages

Toc Lab Manual Pages For Printout

The document describes a lab manual for the Theory of Computation subject. It contains 10 experiments related to designing finite state machines, pushdown automata and Turing machines to recognize various languages. It also includes expected viva questions and figures for each experiment.

Uploaded by

Ketan Soni
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
91 views30 pages

Toc Lab Manual Pages For Printout

The document describes a lab manual for the Theory of Computation subject. It contains 10 experiments related to designing finite state machines, pushdown automata and Turing machines to recognize various languages. It also includes expected viva questions and figures for each experiment.

Uploaded by

Ketan Soni
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/ 30

MAHAKAL INSTITUTE OF TECHNOLOGY, UJJAIN

Approved By: All India Council of Technical Education (New Delhi)

DEPARTMENT OF
COMPUTER SCIENCE AND ENGINEERING

LAB MANUAL

Name of Student :…………………………………..

Enrollment no. …………………………………..

Name of Lab :Theory of Computation

Subject Code : CS- 501

Branch : Computer Science and Engineering

Year/Sem : III/V
INDEX
Sno. Name of Experiment Date Sign Remark

1. Study of JFLAP software

Design a Finite State Machine (FSM) that accepts all


2. strings over input symbols {0, 1} having three
consecutive 1's as a substring.
Design a Finite State Machine (FSM) that accepts all
3. strings over input symbols {0, 1} which are divisible
by 3.
Design a Finite State Machine (FSM) that accepts all
4.
decimal string which are divisible by 3.

5. Construct DFA accepting odd numbers of 0s and 1s

Design a Program to create PDA machine that


6 accept the well-formed parenthesis.

Check string aabbbbbccc is valid for given


7 grammar using JFLAP tool.
Convert CFG to Chomsky Normal form using JFLAP
8 tool.

Construct PDA for the language L= {a n bn: n >


9 0} using JFLAP tool
Construct a Turing machine for the language
10 L = {a n b n c n ,n>=1} using JFLAP.
E1

Fig1

Fig2
Fig3

Fig4
Fig5

Fig 6
Fig7

Fig8
Fig 9
Fig 10

Fig11
Fig12

EXPECTED VIVA QUESTIONS:


Q1. What is JFLAP?
Q2. What is DFA?
Q3. What is difference between NFA and DFA??

NAME OF FACULTY: PROF.PRIYANKA DUBEY


SIGNATURE:
DATE:
Output Set E2
EXPECTED VIVA QUESTIONS:
Q1. What is string?
Q2. What is meaning of “strings over input symbols {0, 1}”?
Q3. Draw FA for given problem?

NAME OF FACULTY: PROF.PRIYANKA DUBEY


SIGNATURE:
DATE:
Output Set E3

EXPECTED VIVA QUESTIONS:


Q1. How to identify which binary number is divisible by 3.
Q2. Draw finite automata for given problem?
Q3. Which type of grammar is accepted by FA.

NAME OF FACULTY: PROF.PRIYANKA DUBEY


SIGNATURE:
DATE:
Output Set E4

EXPECTED VIVA QUESTIONS:


Q1. What is regular expression for string divisible 3?
Q2. List all the binary string which is divisible by 3?

NAME OF FACULTY: PROF.PRIYANKA DUBEY


SIGNATURE:
DATE:
Output Set E5

EXPECTED VIVA QUESTIONS:


Q1. Explain properties of DFA?
Q2. Draw deterministic finite automata for given problem?

NAME OF FACULTY: PROF.PRIYANKA DUBEY


SIGNATURE:
DATE:
Output Set E6

EXPECTED VIVA QUESTIONS:


Q1. What is DPDA and NPDA?
Q2.What type of grammar is accepted by PDA ?

NAME OF FACULTY: PROF.PRIYANKA DUBEY


SIGNATURE:
DATE:
E7

Fig1
Fig2
Fig3
Fig4

EXPECTED VIVA QUESTIONS:


Q1. What is ambiguity of grammar?
Q2. What is parse tree?

NAME OF FACULTY: PROF.PRIYANKA DUBEY


SIGNATURE:
DATE:
E8
EXPECTED VIVA QUESTIONS:
Q1. What is CFG?
Q2. What are the rules’ of chomsky Normal form?

NAME OF FACULTY: PROF.PRIYANKA


DUBEY SIGNATURE:
DATE:
E9

Fig.1

Fig.2
Fig.3

EXPECTED VIVA QUESTIONS:


Q1. What is PDA?
Q2. Which language is accepted by PDA ?
Q3. Draw PDA for given problem ?

NAME OF FACULTY: PROF.PRIYANKA


DUBEY SIGNATURE:
DATE:
E10

Fig1

Fig2
Fig3
Fig4

EXPECTED VIVA QUESTIONS:


Q1. What is turing machine?
Q2. Which language is accepted by TM ?
Q3. Explain Chomsky hierarchy ?

NAME OF FACULTY: PROF.PRIYANKA


DUBEY SIGNATURE:
DATE

You might also like