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

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

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

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

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

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

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

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

1186. ___ pricing reduces price by increasing customer volume.

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

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

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

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

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

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

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

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

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

1192. A shift–reduce parser suffers from .

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

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

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

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

1195. Example of strength reduction in compilers?

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

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

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

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

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

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

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

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