Theory of Computation MCQs – Set 60

By growuppharmacy / June 9, 2025

Theory of Computation MCQs – Set 60

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

1181. NPDA for grammar S→aSS | ab has δ transitions _

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

A. …A… B. …B… C. …C… D. …D…

1182. S1: L₂–L₁ is RE if L₁ recursive, L₂ RE. S2: set of all TMs is countable. Which?

Theory of Computation • Recursion theory • UGC NET Paper 2 Computer Science SEPT 2013

A. S1 correct, S2 not B. Both correct C. Both not D. S1 not, S2 correct

1183. Postfix of infix (A+B^D)/(E−F)+G is ___.

Theory of Computation • Expression conversion • UGC NET Paper 2 Computer Science SEPT 2013

A. ABD^+EF−/G+ B. ABD+^EF−/G+ C. ABD+^EF/G−G+ D. ABD^+EF/G−G+

1184. Shift-Reduce parser: Shift advances by ___ and Reduce ___?

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

A. K>1 symbols; applies grammar to join trees B. 1 symbol; applies grammar to join trees C. K=2 symbols; applies grammar to form tree D. no advance; applies grammar to form tree

1185. Which is true? A. Canonical LR is LR(1). B. All LR(K>1) can be transformed to LR(1).

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

A. A only B. B only C. A & B D. None

1186. ___ pricing reduces price by increasing customer volume.

Theory of Computation • Pricing Models • UGC NET Paper 2 Computer Science SEPT 2013

A. EOQ model B. Inventory C. Data Mining D. Demand-Sensitive Pricing

1187. L₁={aⁿbⁿ | n>1}∪{a}, L₂={w C wᴿ}. Which are deterministic?

Theory of Computation • Deterministic Context-Free Languages • UGC NET Paper 2 Computer Science SEPT 2013

A. n>1}∪{a}, L2={w C wᴿ}. Which deterministic? B. both nondet C. L1 nondet, L2 det D. L1 det, L2 nondet

1188. Given grammars G1 and G2 (as shown), which are ambiguous?

Theory of Computation • Grammar Ambiguity • UGC NET Paper 2 Computer Science SEPT 2013

A. G1 unamb, G2 unamb B. G1 unamb, G2 amb C. G1 amb, G2 unamb D. G1 amb, G2 amb

1189. Match normal forms to grammars: Chomsky (a), Greibach (b), S-grammar (c), LL (d). Answer codes iv–iii–ii–i.

Theory of Computation • Grammar Normal Forms • UGC NET Paper 2 Computer Science SEPT 2013

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

1190. Subgraph-isomorphism and set-partition decision problems are ___.

Theory of Computation • Complexity Classes • UGC NET Paper 2 Computer Science SEPT 2013

A. S1 ∈ NP, S2 ∈ P B. S1 ∈ NP, S2 ∈ NP C. S1 ∈ P, S2 ∈ P D. S1 ∈ P, S2 ∈ NP

1191. Which suffices to convert an arbitrary CFG to LL(1)?

Theory of Computation • Grammar transformation • UGC NET Paper 2 Computer Science SEPT 2013

A. Removing left recursion alone B. Removing left factoring alone C. Removing left recursion and factoring D. None of the above

1192. A shift–reduce parser suffers from .

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

A. shift–reduce conflicts only B. reduce–reduce conflicts only C. both shift–reduce and reduce–reduce conflicts D. shift‐handle and reduce‐handle conflicts

1193. If L is regular then even(L) (chars in even positions) and Chop(L) (remove first 2 chars) are?

Theory of Computation • Regular Languages: Closure • UGC NET Paper 2 Computer Science SEPT 2013

A. even reg, Chop not B. both reg C. even not, Chop reg D. both not

1194. Criticism-free idea generation is a feature of:

Theory of Computation • Decision Support • UGC NET Paper 2 Computer Science SEPT 2013

A. DSS B. GDSS C. ERP D. AI

1195. Example of strength reduction in compilers?

Theory of Computation • Optimization Techniques • UGC NET Paper 2 Computer Science SEPT 2013

A. P+P→2*P B. P*32→P<<5 C. (P<<4)–P→P*15 D. P*0→0

1196. Which regex identities hold? (a)(r+s)=(s+r)* (b)(r*)=r (c)(r* s*)=(r+s).

Theory of Computation • Regular languages • UGC NET Paper 2 Computer Science SEPT 2013

A. (a)&(b) only B. (b)&(c) only C. (c)&(a) only D. (a),(b)&(c)

1197. Turing machine M accepts language L(M) = ?

Theory of Computation • Turing Machines • UGC NET Paper 2 Computer Science SEPT 2013

A. 0*1* B. 00* C. 10* D. 1*0*

1198. For DFA of L=0*10* with all states reachable, equivalence classes = ?

Theory of Computation • Automata: Myhill–Nerode • UGC NET Paper 2 Computer Science SEPT 2013

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

1199. Source {A:½,B:¼,C:⅛,D:⅛}. Huffman avg bits/symbol = ?

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

A. 2 B. 1.75 C. 1.5 D. 1.25

1200. L={0ⁿ1ⁿ}. Which is correct? ¬L CF, Lᵏ CF ∀k

Theory of Computation • Context-Free Languages • UGC NET Paper 2 Computer Science SEPT 2013

A. ¬L CF, Lᵏ CF ∀k B. ¬L not CF, Lᵏ CF ∀k C. Both ¬L and Lᵏ CF D. Both ¬L and Lᵏ not CF

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

M	T	W	T	F	S	S
				1	2	3
4	5	6	7	8	9	10
11	12	13	14	15	16	17
18	19	20	21	22	23	24
25	26	27	28	29	30	31

Theory of Computation MCQs – Set 60

Related Posts