Theory of Computation MCQs – Set 59

By Atul Sahu • Computer Science, Theory of Computation

Theory of Computation MCQs – Set 59

UGC NET Paper 2 Computer Science DEC 2013 – Theory of Computation

1161. Match: a. CFG; b. Regular; c. CSG; d. Unrestricted – i. PDA; ii. DFA; iii. LBA; iv. TM.

Theory of Computation • Automata theory • UGC NET Paper 2 Computer Science DEC 2013

A. ii iv iii i B. ii iv i iii C. iv i ii iii D. i iv iii ii

1162. LRE, LCS, LREC, LCF, LDCF: inclusion chain is

Theory of Computation • Language classes • UGC NET Paper 2 Computer Science DEC 2013

A. LCF⊂LDCF⊂LCS⊂LRE⊂LREC B. LCF⊂LDCF⊂LCS⊂LREC⊂LRE C. LDCF⊂LCF⊂LCS⊂LRE⊂LREC D. LDCF⊂LCF⊂LCS⊂LREC⊂LRE

1163. S1: SLR uses Follow-info; LR/LALR use lookaheads in items. S2: LR grammars ⊃ SLR/LALR. Which?

Theory of Computation • Parsing: LR Variants • UGC NET Paper 2 Computer Science DEC 2013

A. S1 and S2 are true. B. S1 true, S2 false. C. S1 false, S2 true. D. S1 and S2 are false.

1164. A top-down parser uses which derivation scanning left to right?

Theory of Computation • Parsing: Top-Down • UGC NET Paper 2 Computer Science DEC 2013

A. Leftmost B. Leftmost reversed C. Rightmost reversed D. Rightmost

1165. _______ is often used to prove correctness of a recursive function.

Theory of Computation • Proof Techniques • UGC NET Paper 2 Computer Science DEC 2013

A. Diagonalization B. Commutativity C. Mathematical Induction D. Matrix Multiplication

1166. The resolvent of {A∨B, ¬A∨D, C∨¬B} is

Theory of Computation • Resolution • UGC NET Paper 2 Computer Science DEC 2013

A. A∨B B. C∨D C. A∨C D. A∨D

1167. NFA→minimal DFA needs how many states for given table?

Theory of Computation • Automata • UGC NET Paper 2 Computer Science DEC 2013

A. 5 B. 4 C. 3 D. 2

1168. Given L₁ = a* b a a* and L₂ = a b*, the right-quotient L₁/L₂ is:

Theory of Computation • Formal Languages • UGC NET Paper 2 Computer Science DEC 2013

A. a* b B. a* b a a* C. a* b a* D. None

1169. Given grammars G₁ and G₂, which is correct?

Theory of Computation • Parsing • UGC NET Paper 2 Computer Science DEC 2013

A. G₁ amb, G₂ not B. G₁ amb, G₂ amb C. G₁ not, G₂ amb D. G₁ not, G₂ not

1170. A PDA is deterministic if δ(q,a,b) has ≤1 move, and if δ(q,λ,b)≠∅ then δ(q,c,b)=∅ for all c∈Σ.

Theory of Computation • Automata theory • UGC NET Paper 2 Computer Science DEC 2013

A. only first B. only second C. both D. neither

1171. Match grammars to automata: (a) C-sensitive (b) Regular (c) C-free (d) Unrestricted — (i) DFA (ii) PDA (iii) LBA (iv) TM

Theory of Computation • Automata theory • UGC NET Paper 2 Computer Science DEC 2013

A. ii iv i iii B. … C. … D. …

1172. A file of 100 000 chars over {g–l} with frequencies 45k,13k,12k,16k,9k,5k can be Huffman-coded into approximately

Theory of Computation • Coding & compression • UGC NET Paper 2 Computer Science DEC 2013

A. 252 000 bits B. 264 000 bits C. 246 000 bits D. 224 000 bits

1173. s₁: CSL closed under intersection, concatenation, substitution, inverse homomorphism. s₂: CFL closed under complementation, substitution, homomorphism.

Theory of Computation • Formal languages • UGC NET Paper 2 Computer Science DEC 2013

A. both correct B. s₁ correct only C. s₂ correct only D. both incorrect

1174. Horn clauses are propositions with________.

Theory of Computation • Logic programming • UGC NET Paper 2 Computer Science DEC 2013

A. single atomic left side B. multiple atomic left side C. single atomic each side D. single atomic or empty left side

1175. S1: Algorithm exists to decide if CFG’s language is infinite. S2: Algorithm exists to test CFG equivalence. Which hold?

Theory of Computation • Decidability • UGC NET Paper 2 Computer Science DEC 2013

A. S1 true, S2 false B. Both true C. Both false D. S1 false, S2 true

1176. Number of states in minimal DFA for L={aⁿ | n≥4} is ___.

Theory of Computation • DFA Minimization • UGC NET Paper 2 Computer Science DEC 2013

A. n≥4} is . B. 3 C. 4 D. 5

1177. Reg-exp for L={w∈{0,1}* | w has no consecutive zeros} is ___.

Theory of Computation • Regular Languages • UGC NET Paper 2 Computer Science DEC 2013

A. w has no pair of consecutive zeros} is . B. (1+010)* C. (01+10)* D. (1+010)*(0+λ)

1178. 0–1 knapsack via greedy? Fractional via DP? Which?

Theory of Computation • Algorithms • UGC NET Paper 2 Computer Science DEC 2013

A. Both true B. Both false C. 0–1 false, fractional true D. 0–1 true, fractional false

1179. L={aⁿbⁿaᵐbᵐ | n,m≥0} is ________

Theory of Computation • Formal languages • UGC NET Paper 2 Computer Science DEC 2013

A. Context-free but not linear B. Context-free and linear C. Not CF and not linear D. Neither

1180. NPDA M with transitions accepts ________

Theory of Computation • Pushdown automata • UGC NET Paper 2 Computer Science DEC 2013

A. L=abb* a B. {a}∪L(abba) C. L=ab a D. {a}∪L(aba)

Disclaimer for MCQ Quiz
This quiz is for educational purposes only…

0 0 votes

Article Rating

0 Comments

Oldest

Newest Most Voted

Inline Feedbacks

View all comments

Theory of Computation MCQs – Set 59

Related Posts