University Question Paper(Jan 2023)
Total No. of Questions: 5] SEAT No.:
PA-1028
[Total No. of Pages: 2
CS-356 (Theoratical Computer Science Pattern) (CBCS)
Time: 2 Hours
Instructions to the candidates:
1) All questions are compulsory.
2) Figures to the right indicate full marks.
[Max. Marks: 35
Q1) Attempt any EIGHT of the following (Out of TEN) [8 × 1 = 8]
a) Define Unit production of grammar, 23
b) Construct Melay machine which toggles its input down
c) Explain proper Suffix and Prefix of a string with one example.
d) Give formal definition of Push Automata.
e) Define left linear and right linear grammar.
f) State True or False Finite Automata has an infinite number of states.
g) Name the types of normal forms of grammar.
h) Write the tuples of LBA.
i) State true or false. Pumping lemma is used to show that language is not context tree.
j) Write smallest possible string accepted by the following regular expression.
10+ (0+11)0*1
Q2) Attempt any FOUR of the following (Out of FIVE) [2 x 4 = 8]
a) Explain types of grammar.
b) Construct FA for regular expression. (01+10)*+11
c) Differentiate between FA and PDA (any two points)
d)Write down the e-closure of each state from the following FA.
start→⃝q0→⃝q1→⃝q2
e) Define types of Turing Machine.
03) Attempt any TWO of the following (Out of THREE). [2 x 4 =8]
a)Construct a DFA for a language
LI↷L2
LI= All strings starting with 'a'}
L2={ All strings not having 'ab' as substring}
b) Construct the following CFG into Normal Form (CNF)
S-> ABA
A-> aA |ε
B-> bB|ε
c) Design TM for language..
L {WCWR|W is in (0+1)*)}
04) Attempt any TWO of the following (Out of THREE).
a) Construct a PDA for the language
L= (01m2 nm | n,m>=1}
b) Construct a Moore machine for the language L over ∑={0,1}which outputs '*' if the string contains '11' in it and outputs '#' otherwise.
c) Compare DFA and NFA.
Q5) Attempt any ONE of the following (Out of TWO). [1 × 3 = 3]
a) Construct a Mealy machine to convert each occurrence of substring 101 by 100 over alphabet {0.1}.
b) Show that L= {0n1n| n>=1) is not regular..
THANKS!!!
0 Comments