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

DR. BABASAHEB AMBEDKAR TECHNOLOGICAL UNIVERSITY, LONERE

Mid Semester Examination – Oct 2019

Course: B. Tech in Computer Sci. & Engineering Sem: V

--- Content provided by FirstRanker.com ---

Subject Name: Theory of Computation Max Marks: 20

Subject Code: BTCOC502 Duration: 1 Hr.

Instructions to the Students: Date: -7/10/2019-

1. Assume suitable data, if necessary.
2. Attempt all the questions.

--- Content provided by FirstRanker.com ---

Q.1 Select the correct option. 6+1=6 Marks

1. L denotes the language over {a}, finite language of symbols.
   1. string
   2. characters
   3. integers
   4. DFA

   --- Content provided by FirstRanker.com ---

2. Transition diagrams are represented by
   1. ellipses
   2. circles
   3. triangles
   4. rectangles

   --- Content provided by FirstRanker.com ---

3. Grammar that produce more than one parse tree for same sentence is:
   1. Ambigious
   2. Unambiguous
   3. Complementation
   4. Concatentation Intersection

   --- Content provided by FirstRanker.com ---

4. Regular grammars also known as
   1. Type 0
   2. Type 1
   3. Type 2
   4. Type 3

   --- Content provided by FirstRanker.com ---

5. Lets read r are regular expressions denoting the languages R and S. Then r(r+s)* denotes.
   1. S +RS
   2. R+
   3. RUS
   4. R*

   --- Content provided by FirstRanker.com ---

6. S→aAS is which grammar?
   1. Right linear Grammar
   2. Left linear Grammar
   3. Linear Grammar
   4. None of the above

   --- Content provided by FirstRanker.com ---

Q.2 Solve Any Two of the following: 2*6=12 Marks

1. Construct the DFA for L = {a, ab}.
   1. w: strings starting and ending with different characters
   2. w: string with "ab" as substring

--- Content provided by FirstRanker.com ---

2. Show that following grammar is ambiguous for the input "a+a*a"

   S→SS | aS | Sa | a

3. Construct the regular Grammar for the given finite automata.

Q.3 Any One of the following: 1*8 = 8 Marks

1. What are the requirements of verification methods of Context Free Grammar? With suitable example, explain them individually.

--- Content provided by FirstRanker.com ---

2. 1. Construct the moore machine corresponding to the mealy machine.
   2. Convert following moore machine to mealy machine.

*** End ***

FirstRanker.com

--- Content provided by FirstRanker.com ---