Question bank for
First IAT covering 1.5 Module
Name of the faculty: Gouri Patil / Margesh K
Sem: V A and B Subject: ATC Subject code:17CS54
|
Sl.No.
|
Question
|
Blooms Taxonomy Level
|
CO
|
PO
|
|||||||||||||||||||||
|
1
|
Define DFA, NFA, є-NFA,
Regular expressions
|
1
|
1
|
1,6,8
|
|||||||||||||||||||||
|
2
|
List the hierarchy of languages.
|
1
|
1
|
1,6,8
|
|||||||||||||||||||||
|
3
|
Show that if ∑ ≠Ф
then ∑* is countably infinite
|
2
|
1
|
1,6,8
|
|||||||||||||||||||||
|
4
|
Compare DFSM and NDFSM
|
2
|
1
|
1,6,8
|
|||||||||||||||||||||
|
5
|
Construct DFA to
accepts a strings of 0’s ,1’s and 2’s beginnig with 0 followed by odd number
of 1’s and ending with 2
|
3
|
2
|
1,2,3,4,7,8,9,10,12
|
|||||||||||||||||||||
|
6
|
Construct DFA to accept strings of a’s and b’s having a sub string aa
|
3
|
2
|
1,2,3,4,7,8,9,10,12
|
|||||||||||||||||||||
|
7
|
Construct DFA to accept strings of a’s and b’s having even
number of a’s and odd number of b’s.
|
3
|
2
|
1,2,3,4,7,8,9,10,12
|
|||||||||||||||||||||
|
8
|
Construct є-NFA
to accept the following language L = {w | w є abab n or aba n where n є
0}
|
3
|
2
|
1,2,3,4,7,8,9,10,12
|
|||||||||||||||||||||
|
9
|
Simplify DFA using table filling algorithm
|
3
|
2
|
1,2,3,4,7,8,9,10,12
|
|||||||||||||||||||||
|
10
|
Simplify above DFA using splitting method
|
3
|
2
|
1,2,3,4,7,8,9,10,12
|
|||||||||||||||||||||
|
| |||||||||||||||||||||||||
|
11
|
Simplify RE using Kleen star
    |
3
|
2
|
1,2,3,4,7,8,9,10,12
|
|||||||||||||||||||||
|
12
|
Prove that if M be a FA recognizing the language L, then
there exists an equivalent regular expression R for the regular language L
such that L=L(R)
Hint: Kleen’s theorem
|
4
|
3
|
1,2,3,4,8,9,10,12
|
|||||||||||||||||||||
|
13
|
Classify various languages by hierarchy
|
4
|
3
|
|
|||||||||||||||||||||
|
14
|
Choose one of design technique to write DFSM
L = {w | w є
{a,b}*, No two consecutive characters are same}
|
5
|
4
|
1,2,3,4,8,9,10,12
|
|||||||||||||||||||||
|
15
|
Choose one of design technique to write DFSM
to accept decimal strings divisible by 3
|
5
|
4
|
1,2,3,4,8,9,10,12
|
|||||||||||||||||||||
|
16
|
Choose one of design technique to write DFSM
L = {w : |w| mod3= 0}
|
5
|
4
|
1,2,3,4,8,9,10,12
|
|||||||||||||||||||||
|
17
|
Design DFSM to accept strings of a’s and b’s having even
number a’s and odd number of b’s
|
6
|
5
|
|
|||||||||||||||||||||
|
18
|
Design DFA from є-NFA
|
6
|
5
|
1,2,3,4,8,9,10,12
|
|||||||||||||||||||||
|
| |||||||||||||||||||||||||
|
19
|
Design a regular expression for
L={anbn : (m+n) is even}
L={a2nb2m: n,m≥0}
L={anbm: n≥4,
m≤3}
|
6
|
5
|
1,2,3,4,8,9,10,12
|
|||||||||||||||||||||
|
|
|
|
|
|
No comments:
Post a Comment