Theory of Computation MCQs – Set 58

By Atul Sahu • Computer Science, Theory of Computation

Theory of Computation MCQs – Set 58

UGC NET Paper 2 Computer Science JUNE 2010 – Theory of Computation

1141. MLM recognizes: (i)a (ii)aba (iii)abaabaaba (iv)abaaba… Compare regex (i) (aba)³ˣ; (ii) a.(baa)³ˣ–1.ba; (iii) ab.(aab).³ˣ–1.a

Theory of Computation • Regular Expressions • UGC NET Paper 2 Computer Science JUNE 2010

A. (ii)&(iii) same, (i) diff B. (ii)&(iii) not same C. (i),(ii),(iii) diff D. (i),(ii),(iii) same

1142. “M-Commerce” refers to

Theory of Computation • E-Commerce • UGC NET Paper 2 Computer Science JUNE 2010

A. myth B. mobile business reach C. large memory trade D. none

1143. Most valuable e-commerce long-term for customer is

Theory of Computation • E-Commerce • UGC NET Paper 2 Computer Science JUNE 2010

A. B2C B. B2B C. C2C D. none

1144. Principal e-payment systems include

Theory of Computation • E-Payments • UGC NET Paper 2 Computer Science JUNE 2010

A. credit card B. digital wallet C. electronic cheque D. all

1145. Minimum number of states for an NFA recognizing {ab·a·bⁿ ∪ ab·aⁿ}?

Theory of Computation • Automata: NFA State Complexity • UGC NET Paper 2 Computer Science JUNE 2010

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

1146. __________ is extracting actionable information from large data.

Theory of Computation • Data Mining • UGC NET Paper 2 Computer Science JUNE 2010

A. Data Management B. C. Data Mining D. Metadata

1147. Eco system is a Framework for

Theory of Computation • E-Business • UGC NET Paper 2 Computer Science JUNE 2010

A. Building a Computer System B. Building Internet Market C. Building Offline Market D. Building Market

1148. Which is false for regular languages?

Theory of Computation • Formal Language Closures • UGC NET Paper 2 Computer Science JUNE 2010

A. Closed under homomorphism B. Not closed under inverse homomorphism C. Closed under quotient D. Closed under substitution

1149. Which holds? (i) Recursively enumerable sets closed under complement? (ii) Recursive sets closed under complement?

Theory of Computation • Language Closures • UGC NET Paper 2 Computer Science JUNE 2010

A. only (i) B. only (ii) C. both D. neither

1150. Skolemization is:

Theory of Computation • Logic Transformation • UGC NET Paper 2 Computer Science JUNE 2010

A. bringing quantifiers to front B. removing universals C. removing existentials D. all of the above

1151. If parse-tree depth ≤ i in CNF grammar, word length ≤:

Theory of Computation • Parsing Complexity • UGC NET Paper 2 Computer Science JUNE 2010

A. 2^{i+1} B. 2^i C. 2^{i−1} D. i

1152. Match mobile computing: (a) Downlink control (b) Radio data rate (c) User’s stay in cell (d) FDDI bandwidth — (1) 100 Mbps (2) 2 Mbps (3) BS→MD (4) residency latency

Theory of Computation • Performance Metrics • UGC NET Paper 2 Computer Science JUNE 2010

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

1153. Which regular-expression identity is true?

Theory of Computation • Regular Expressions • UGC NET Paper 2 Computer Science JUNE 2010

A. (r+s)* = r*·s* B. (r+s)* = r*+s* C. (r+s)* = (r*·s*)* D. r*·s* = r*+s*

1154. RegExp (a+b)^n ⇒ minimal DFA states =:?

Theory of Computation • Automata State Complexity • UGC NET Paper 2 Computer Science JUNE 2010

A. n B. n+1 C. n+2 D. 2^n

1155. Which holds? DFA≡NFA power; DPDA≡NPDA power?

Theory of Computation • Automata Theory • UGC NET Paper 2 Computer Science JUNE 2010

A. Both true B. Only DFA=NFA C. Only DPDA=NPDA D. Neither

1156. Regular expression for DFA is:?

Theory of Computation • Automata to Regex • UGC NET Paper 2 Computer Science JUNE 2010

A. ab*(b+aa*b)* B. … C. … D. …

1157. Match grammars to automata: Regular→DFA, CFL→PDA, CSL→LBA, Unrestricted→TM:

Theory of Computation • Chomsky Hierarchy • UGC NET Paper 2 Computer Science JUNE 2010

A. c,a,b,d B. c,a,d,b C. c,b,a,d D. c,b,d,a

1158. Which are not in Greibach Normal Form among productions i,ii,iii?

Theory of Computation • Grammar Normal Forms • UGC NET Paper 2 Computer Science JUNE 2010

A. i&ii B. i&iii C. ii&iii D. i,ii&iii

1159. An equivalent grammar to S→aA,A→BB,B→aBb is:?

Theory of Computation • Grammar Transformations • UGC NET Paper 2 Computer Science JUNE 2010

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

1160. Which is not correct? Every CSL is recursive; there is a recursive language not CSL.

Theory of Computation • Language Hierarchy • UGC NET Paper 2 Computer Science JUNE 2010

A. i true, ii false B. Both true C. Both false D. i false, ii true

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 58

Related Posts