Th Of Computation Dec 2002
This document was uploaded by user and they confirmed that they have the permission to share it. If you are author or own the copyright of this book, please report to us by using this DMCA report form. Report DMCA
Overview
Download & View Th Of Computation Dec 2002 as PDF for free.
More details
- Words: 261
- Pages: 3
2.
56 7.
3.
B. E. (Coll1puter ~cie~ce EngiJ;l~~g) VIth Seinest~r Examination, Deeember-:-2002 THEORY OF COMPUTATION Paper-CSE-31O-C Maximum Marks: 100
Time allowed: 3 hours Note: Attempt any five of the following. 1.
Describe the finite state automation by illustrating with transition diagram. Consider fsm whose transition function 8 is given in the form of a transition table Q = {'lo, q) , q2' q3}, L = {O, I}, F = {'lo} Give the entire sequence of states for input string 110001 States
~@
"
Input 0
1
q2
q)
q)
q3
qo
q2
q3
q3
q\
q2
20
4.
Explain Moore machines. How FA can be converted into 20 Moore machines?
3.
Explain the algorithm for minimization of FA ? Explain the closure properties of regular sets.
4.
20
Explain the following: (a) Chomsky Normal Form with examples 567400P2(Q-8)
P.T. G.
(2)
(6 yo Construct a regular ··expression corresponding to the _ ,.
;. i
state diagram .
10,10
s.
Explain Push Down Automata and their application in details.
20
What is Thring Machine? Explain advantages of TM over FSM.(Finite State Macl'ine). If L is a regular set over L·, then L - L is also a regular •over L.
10,10
Expl;rin Chomsky Hierarchies of Grammars. Design a Turing Machine over {I, b} which can compute concatenation function oyer L = { 1 }. If a pair of words (WI' W2) is the input, the output has to be WI W2• 10,10 8 ... Describe briefly the following: (a) Context Sensitive Language (b) Universal Turing Machine (c) Undeciability.
567-400
5,8,7
56 7.
3.
B. E. (Coll1puter ~cie~ce EngiJ;l~~g) VIth Seinest~r Examination, Deeember-:-2002 THEORY OF COMPUTATION Paper-CSE-31O-C Maximum Marks: 100
Time allowed: 3 hours Note: Attempt any five of the following. 1.
Describe the finite state automation by illustrating with transition diagram. Consider fsm whose transition function 8 is given in the form of a transition table Q = {'lo, q) , q2' q3}, L = {O, I}, F = {'lo} Give the entire sequence of states for input string 110001 States
~@
"
Input 0
1
q2
q)
q)
q3
qo
q2
q3
q3
q\
q2
20
4.
Explain Moore machines. How FA can be converted into 20 Moore machines?
3.
Explain the algorithm for minimization of FA ? Explain the closure properties of regular sets.
4.
20
Explain the following: (a) Chomsky Normal Form with examples 567400P2(Q-8)
P.T. G.
(2)
(6 yo Construct a regular ··expression corresponding to the _ ,.
;. i
state diagram .
10,10
s.
Explain Push Down Automata and their application in details.
20
What is Thring Machine? Explain advantages of TM over FSM.(Finite State Macl'ine). If L is a regular set over L·, then L - L is also a regular •over L.
10,10
Expl;rin Chomsky Hierarchies of Grammars. Design a Turing Machine over {I, b} which can compute concatenation function oyer L = { 1 }. If a pair of words (WI' W2) is the input, the output has to be WI W2• 10,10 8 ... Describe briefly the following: (a) Context Sensitive Language (b) Universal Turing Machine (c) Undeciability.
567-400
5,8,7
Related Documents
Th Of Computation Dec 2002
November 2019 9
Th Of Computation
November 2019 9
Kepmen 58 Th 2002
June 2020 5
Computation
November 2019 22
Comp Network Dec 2002
November 2019 18