# Applications of Pumping Lemma/Pigeonhole principle Online Exam Quiz

Applications of Pumping Lemma/Pigeonhole principle GK Quiz. Question and Answers related to Applications of Pumping Lemma/Pigeonhole principle. MCQ (Multiple Choice Questions with answers about Applications of Pumping Lemma/Pigeonhole principle

### An exact cover problem can be represented using:

Options

A : incidence matrix

B : bipartite graph

C : both (a) and (b)

D : none of the mentioned

### For which of the following, greedy algorithm finds a minimal vertex cover in polynomial time?

Options

A : tree graphs

B : bipartite graphs

C : both (a) and (b)

D : none of the mentioned

### If n objects are distributed over m places, and n < m, then some of the places receive:

Options

A : at least 2 objects

B : at most 2 objects

C : no object

D : none of the mentioned

### Which of the following can refer a language to be non regular?

Options

A : Pumping Lemma

B : Myphill Nerode

C : Both (a) and (b)

D : None of the mentioned

### Which of the following fields may have pigeonhole principle violated?

Options

A : Discrete mathematics

B : Computer Science

C : Quantum Mechanics

D : None of the mentioned

### Which of the following is not an application of Pumping Lemma?

Options

A : {0i1i|i>=0}

B : {0ix|i>=0, x?{0, 1}* and |x|<=i}

C : {0n| n is prime}

D : None of the mentioned

### Which of the following is not an example of counting argument?

Options

A : Pigeonhole principle

B : Dirichlet's drawer principle

C : Dirichlet's box principle

D : None of the mentioned

### Which of the following problems do not belong to Karp's 21 NP-complete problems?

Options

A : Vertex Cover problems

B : Knapsack

C : 0-1 integer programming

D : None of the mentioned

### Which of the following problems were reduced to Knapsack?

Options

A : Exact Cover

B : Max Cut

C : 0-1 integer programming

D : None of the mentioned

### Which of the given problems are NP-complete?

Options

A : Node cover problems

B : Directed Hamilton Circuit Problem

C : Both (a) and (b)

D : None of the mentioned

### Ambiguous Grammar more Online Exam Quiz

Semantic Net - 2

Ambiguous Grammar

Applications - Parsers

Applications of DFA

Applications of NFA

CFG-Eliminating Useless Symbols

Deterministic Finite Automata-Introduction and Definition

Finding Patterns in Text,Algebric Laws and Derivatives

From Grammars to Push Down Automata

Node-Cover Problem, Hamilton Circuit Problem