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

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

Q.2
(A)
(B)
"(0
DR. BABASAHEB AMBEDKAR TECHNOLOGICAL UNIVERSITY, LONERE
? 1 Mid Semester Examination? Oct 2019
Course: B. Tech in Computer Sci. & Engineering Sem: V
Subject Name: Theory of Computation Subject Code: BTCOC502
Max Marks:20 DatebW D11ration:- 1 Hr.
Instructions to the Students: 5-74 0 6+ ?10?
1. Figures to the right indicate marks.
2. Assume suitable data.
Select the correct option. 6*l= 6 Marks
1. is a ?nite sequence of symbols.
__..._.._._..______._
a. Language b. grammar c. string d. NFA
_ 2. in trans1t10n d1 gains states are represented by_
a.e111pses ? L b cu'cles I ? c. tnangles ? 1; (ii 1ectangles
3. Grammar that produce more than one Parse tree for same sentence is: '
a. Ambiguous b. Uhambiguous c. Complementation d. Concatenation Intersection
4. Regular grammars also known as ____________ grammar.
a. Type 0 b. Type 1 " . c. Type 2 d. Type3
5. Let r and s are regular expressions denoting the languages R and S.
. Then (r + 5) denotes
a. RS b. R* c. RUS d. R+
6. S -> ahS S ?> a is?which grammar ?
a Right Linear Grammar b. Le? Linear Grammar? c. Linear Grammar d. None of the above
Solve Any Two of the foliowing. ? i I 2*3=6 Mark
Construct the DFA ( Z= a,b)
i) w= Strings starting and ending with diffe1ent characters
1 ii) w= suing with ?aab? as substring
Show that following grammar is ambiguous for the input ? a* a+a?
S$S+S|S- S|S*S|S/S|(S)|a
Construet the regular Grammar for the given finite Automata:
Page i 1 /2

Q. 3 Solve Any One of the following.
(A) What are the preliminary simpli?cation methods of Context F ree Grammar?
With suitable example, explain these methods.
(B) 1. Construct the moore machine corresponding to the mealy machine
2; Convex} fOVHOV-?iilg? mabre machine to ihealy machine
State ? _ 0 i i i 1 Output
-) Q0 Q3 _ Q1 0
Q1 Q1 Q2 ? ?1
Q2 ' Q2 Q3 0 i ?
Q3 . Q3 Q0 0
*** End ***
l*8= 8M
Page | 2