Download DBATU B.Tech 2019 Oct-Nov CSE 5th Sem Theory Of Computation Question Paper

Download DBATU (Dr. Babasaheb Ambedkar Technological University) B Tech 2019 Oct-Nov (Bachelor of Technology) CSE 5th Sem Theory Of Computation Question Paper

DR. BABASAHEB AMBEDKAR TECHNOLOGICAL UNIVERSITY, LONERE? ' ?
, Mid Semester Examination 5 Oct 2019
'Course: B'. Tech in Computer Sci. & Engineering Sem: V
Subject Name: Theory of Computation ' l , Subject Code: BTCOC502
Max Marks:20 Date:- 24th Sept 2019 Duration:- '1 Hr. , ?
. Q.2
(A)
(B)
? (C)
Instructions to the Students:
1. Figures to the right indicate marks.
2. Assume suitable data.
Select the correct option. 6*1=6 N.
1. _______________ is a set of strings.
a. Language 13. grammar c. NFA d. DFA
2. . Let r and s are regular expressions denoting the languages R and S. Then (1' 5) denotes; _ __ _
3. RS b. R* c. RUS d. R+
3. In transition diagrams a state pointed by an arrow represents the _ _ _?_ _ _ _ state.
a. ?nal b. interior 0. start d. ?nal or start
4. _ _? _? ___________ grammar is also known as Type 3 grammar. ?
a. unrestricted b. context free c. context sensitive ? d. regular grammat
? 5. Grammar that produce more than one Parse tree for same sentence is:
a. Ambiguous b. Unambiguous c. Complementation d. Intersection
6. ?S ?-> Sab S ?) a ' is which grammar ?
a. Right Linear Grammar b. Le? Linear Grammar c. Linear Grammar (1. None of the above
?Solve Any Two of the following. - I V . 2*3 ?= 6
Construct the DFA'( Z = 0 ,1 )
i) w= Strings starting and ending with same characters
' ii) w= string with ?101? as substring ?
Consider following Grammar:
$9 AlB
A-) CA | epsilon
B9 IE I OB | epsilon
Give the leftmost derivation for the inputs:
1) 00101 2)1001 _
Construct the regular Grammar for the given ?nite Automata:
aW
Page I

? Q. 3 Solve Any One of the following. . ? V , ? ?1'853 Ma
? (A) What IS pumping lemma technique? ' ? ,
Using pumping lemma show that L= {an b11 | n>=1}' 1s not regular language. ? , , ;
(B) ? Convert Following NFA to DFA
1)? .
state ? 0 1
-) a {a,b} {a}
b . {e} {c}
c {d} -
* d? {d} - {d}
? state > 0 >1
9 p {w} ? {q}
*q {r} ' {tbr}
{s} {p}
*s . -- ? {Pl
id": End *itfk,
Page| 2