GPL - Gate Question |

X Close

You need to enable javascript to view this page properly.

Branch

All

Loading

433.

Consider the following two problems on undirected graphs:
α: Given G(V,E), does G have an independent set of size |V|− 4?
β: Given G(V,E), does G have an independent set of size 5?
Which one of the following is TRUE? [2 marks]
(a) α is in P and β is NP-complete
(b) α is NP-complete and β is in P
(c) Both α and β are NP-complete
(d) Both α and β are in P

asked in Computer Science And Engineering, 2005

View Comments [0 Reply]
434.

Consider the languages:
L₁ = {ww^R | wε {0,1}*}
L₂ = {w#w^R | wε {0,1}*}, where # is a special symbol
L₃ = {ww | wε {0,1}*}
Which one of the following is TRUE? [2 marks]
(a) L₁ is a deterministic CFL
(b) L₂ is a deterministic CFL
(c) L₃ is a CFL, but not a deterministic CFL
(d) L₃ is a deterministic CFL

asked in Computer Science And Engineering, 2005

View Comments [0 Reply]
435.

Let L₁ be a recursive language, and let L₂ be a recursively enumerable but not a recursive language. Which one of the following is TRUE? [2 marks]
(a) L₁ is recursive and L₂ is recursively enumerable
(b) L₁ is recursive and L₂ is not recursively enumerable
(c) L₁ and L₂ are recursively enumerable
(d) L₁ is recursively enumerable and L₂ is recursive

asked in Computer Science And Engineering, 2005

View Comments [0 Reply]
436.

Consider the languages:
L1 = {aⁿbⁿc^m |n,m>0} and L2 = {aⁿb^mc^m | n,m > 0 }
Which one of the following statements is FALSE? [2 marks]
(a) L1 ∩ L2 is a context-free language
(b) L1 ∪ L2 is a context-free language
(c) L1 and L2 are context-free languages
(d) L1 ∩ L2 is a context sensitive language

asked in Computer Science And Engineering, 2005

View Comments [0 Reply]
437.

Let N_f and N_p denote the classes of languages accepted by non-deterministic finite automata and non-deterministic push-down automata, respectively. Let D_fand D_p denote the classes of languages accepted by deterministic finite automata and deterministic push-down automata respectively. Which one of the following is TRUE?
[2 marks]
(a) D_f ⊂N_f and D_p ⊂N_p
(b) D_f ⊂N_f and D_p = N_p
(c) D_f =N_f and D_p =N_p
(d) D_f =N_f and D_p ⊂N_p

asked in Computer Science And Engineering, 2005

View Comments [0 Reply]
438.

Consider the machine M:

The language recognized by M is: [2 marks]
(a) {w ε {a,b} * every a in w is followed by exactly two b's}
(b) {w ε {a,b} * every a in w is followed by at least two b's}
(c) {w ε {a,b} * w contains the substring 'abb'}
(d) {w ε {a,b} * w does not contain 'aa' as a substring}

asked in Computer Science And Engineering, 2005

View Comments [0 Reply]

801 1 ...‹‹71 7273 74 75 ›› ... 134

High Frequency Word List with Mnemonics

GPL Dictionary is fast way to learn words with mnemonics.
It contains high frequency word list which are mostly asked in various examinations.
It is dedicated for student appearing for PSUs, GRE, UPSC or any other exams in which vocabulary test is taken.
User can save their own mnemonics (key and link).

Check Now