GPL - Gate Question |

X Close

You need to enable javascript to view this page properly.

Branch

All

Loading

373.

Consider the regular language L = (111 + 11111) *. The minimum number of states in any DFA accepting this languages is: [2 marks]
(A) 3
(B) 5
(C) 8
(D) 9

asked in Computer Science And Engineering, 2006

View Comments [0 Reply]
374.

Let L₁ be a regular language, L₂ be a deterministic context-free language and L₃ a recursively enumerable, but not recursive, language. Which one of the following statements is false? [2 marks]
(A) L₁ ∩ L₂ is a deterministic CFL
(B) L₃ ∩ L₁ is recursive
(C) L₁ ∪ L₂ is context free
(D) L₁ ∩L₂ ∩L₃ is recursively enumerable

asked in Computer Science And Engineering, 2006

View Comments [0 Reply]
375.

If s is a string over (0+1 )* then let n_o(s) denote the number of 0’s in s and n₁(s) the number of 1’s in s. Which one of the following languages is not regular? [2 marks]

asked in Computer Science And Engineering, 2006

View Comments [0 Reply]
376.

Consider the following statements about the context free grammar
G = {S → SS,S → ab,S → ba,S → ∈}
I. G is ambiguous
II. G produces all strings with equal number of a’s and b’s
III. G can be accepted by a deterministic PDA.
Which combination below expresses all the true statements about G? [2 marks]
(A) I only
(B) I and III only
(C) II and III only
(D) I, II and III

asked in Computer Science And Engineering, 2006

View Comments [0 Reply]
377.

Let SHAM3 be the problem of finding a Hamiltonian cycle in a graph G = (V,E) with |V| divisible by 3 and DHAM₃ be the problem of determining if a Hamiltonian cycle exists in such graphs. Which one of the following is true? [2 marks]
(A) Both DHAM₃ and SHAM₃ are NP-hard
(B) SHAM₃ is NP-hard, but DHAM₃ is not
(C) DHAM₃ is NP-hard, but SHAM₃ is not
(D) Neither DHAM₃ nor SHAM₃ is NP-hard

asked in Computer Science And Engineering, 2006

View Comments [0 Reply]
378.

For S ∈ (0 + 1)^* let d (s) denote the decimal value of s (e.g. d (101) = 5).
Let L = {s ∈ (0 + 1)^* d (s)mod5 = 2 and d (s)mod7 ≠4}
Which one of the following statements is true? [2 marks]
(A) L is recursively enumerable, but not recursive
(B) L is recursive, but not context-free
(C) L is context-free, but not regular
(D) L is regular

asked in Computer Science And Engineering, 2006

View Comments [0 Reply]

801 1 ...‹‹61 6263 64 65 ›› ... 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