Scribd
Upload
12 views4 pages

Module 1

This document is a question bank for the Theory of Computation subject at Vijaya Vittala Institute of Technology. It includes various questions related to concepts like alphabets, strings, DFAs, NFAs, and specific language design tasks. The questions are categorized by cognitive levels and are intended for students to demonstrate their understanding of computational theory.

Uploaded by

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

Module 1

This document is a question bank for the Theory of Computation subject at Vijaya Vittala Institute of Technology. It includes various questions related to concepts like alphabets, strings, DFAs, NFAs, and specific language design tasks. The questions are categorized by cognitive levels and are intended for students to demonstrate their understanding of computational theory.

Uploaded by

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

VIJAYA VITTALA INSTITUE OF TECHNOLOGY

#35/1, DoddaGubbiPost, Hennur-Bagalur Road, Bangaluru-560077


(Affiliated to Visvesvaraya Technological University, Belagavi,
Recognized by Govt of Karnataka and Approved by AICTE, New Delhi)

Department of Artificial Intelligence and Machine Learning

Subject Name : Theory Of Computation DATE:


Subject Code : BCS503

MODULE 1-Question Bank

SL.N Questions CO RBT


O

1. Make use of suitable examples to explain the following terms: CO1 L2

a. Alphabets

b. Strings

c. Empty Strings

d. Length of a string

e. Power of an alphabet

f. Concatenation of strings

g. Language

2. Identify the differences between DFA, NFA and ϵ-NFA with Examples. CO1 L1

3. Design a DFSM to accept each of the following languages: CO1 L3

i). L= {wϵ{0,1}* : w has 001 as a substring}

ii). L={ aWa| W€(a+b)*}

iii). L={w | w is of even length and begins with 01}


iv). L={w:|w| mod 5< 3} where w €{a,b}*

v). L={wϵ{a,b}* :every a region in w is of even length.

vi) L={ wϵ{a,b}* : every a is immediately followed by b.

vii) L= {w: na(w)mod5 < 3 } where wϵ{a,b}*

4. Obtain a DFA to accept strings of a’s and b’s having CO1 L3

i) even number of a’s and even number b’s


ii) ii) odd number of a’s and odd number of b’s
iii) iii) even number of a’s and odd number b’s
iv) iv) odd number of a’s and even number b’s

5. Construct a DFA which accepts a set of all binary strings divisible 3 or CO1 L3
binary strings divisible 5

6. CO1 L3
Design a DFA to accept set of all strings on the alphabet ={0,1} that either begins or ends or both with

7. Design an NFA for the given keywords web and ebay and convert it into CO1 L3
DFA

8. Design the NFA for the following transition table CO1 L3

9. CO1 L3
Design an NFA with no more than 5 states for the following language. L={ababn |n0} {aban |n0}

10. Construct the DFA for the following NFA using subset construction CO1 L3
method.
11. Construct the DFA for the following NFA using lazy evaluation method. CO1 L3

12. Obtain the DFA for the following NFA using subset construction method CO1 L3

13. Construct the DFA for the following NFA using Lazy method CO1 L3

14. Obtain the DFA for the following ϵ-NFA . CO1 L3

15. Show that A language L is accepted by some ∈-NFA if and only if L is CO1 L1
accepted by some DFA

16. Obtain the DFA for the following ∈-NFA CO1 L3


17. Prove that CO1 L3

Faculty Name

Prof. Sindhu K

You might also like