1. What does NP stands for in complexity classes theory?

a) Non polynomial

b) Non-deterministic polynomial

c) Both (a) and (b)

d) None of the mentioned

### View Answer

### View Answer

Explanation: NP is said to be one of the most fundamental complexity classes. NP is an acronym for Non deterministic polynomial time.

2. A ___________ is a multi tape turing machine whose input tape is read only.

a) Counter Machine

b) Multi-stack

c) Alternating Turing machine

d) None of the mentioned

### View Answer

### View Answer

Explanation: Counter machines are offline(a multitape turing machine whose input is read only) whose storage tapes are semi-infinite and whose tape symbols contains only two symbols Z and a blank symbol B.

3. Which of the following can generate Unrestricted grammars?

a) Pentonnen Normal form

b) Floyd Normal form

c) Greibach Normal form

d) None of the mentioned

### View Answer

### View Answer

Explanation: Pentonnen Normal form(for Unrestricted grammars) is a special case where there is a slight modification in the format of Kuroda Normal form.

AB->AD

A->BC

A->a

a) tape alphabets

b) number of tapes

c) number of states

d) none of these

### View Answer

### View Answer

Explanation: Another procedure to restrict a turing machine is to limit the size of tape alphabet or reduce the number of states. If the tape alphabets, number of tapes or number of states are limited, then there is only a finite number of different turing machine, so the restricted model is more powerful than the original one.

a) Subset Construction Method

b) Power Set Construction Method

c) Thompson Construction Method

d) Scott Construction Method

### View Answer

### View Answer

Explanation: Thompson Construction method is used to turn a regular expression in an NFA by fragmenting the given regular expression through the operations performed on the input alphabets.

a) Quick Sort

b) Bucket Sort

c) Radix Sort

d) Merge Sort

### View Answer

### View Answer

Explanation: Quicksort is the method of choice in many applications( Unix sort command) with O(nlogn) in worst case.

a) travelling salesman problem

b) halting problem

c) hitting set

d) none of the mentioned

### View Answer

### View Answer

Explanation: Hamilton circuit problem is a special case of travelling salesman problem, obtained by setting the distance between two cities to one if they are adjacent and two otherwise, and verifying that the total distance travelled is equal to n (if so, the route is a Hamiltonian circuit; if there is no Hamiltonian circuit then the shortest route will be longer).

a) Context free

b) Not context free

c) Regular

d) None of the mentioned

### View Answer

### View Answer

Explanation: The pumping lemma is often used to prove that a given language L is non-context-free, by showing that arbitrarily long strings s are in L that cannot be “pumped” without producing strings outside L.

a) Minecraft

b) Minesweeper

c) Dwarf Fortress

d) All of the mentioned

### View Answer

### View Answer

Explanation: Many games fall under the category og turing complete:

a) Minecraft

b) Minesweeper

c) Dwarf Fortress

d) Conway’s Game of Life

e) Pokemon Yellow, etc.

a) It is recursively ennumerable

b) It is undecidable

c) Both (a) and (b)

d) None of the mentioned

### View Answer

### View Answer

Explanation: Halting problem: Does a given Turing machine M halt on a given input w?

a) a total turing machine exists

b) a turing machine that halts for every input

c) turing machine rejects if the input does not belong to the language

d) all of the mentioned

### View Answer

### View Answer

Explanation: A formal language is called recursive if it is a recursive subset of the set of all possible finite sequences over the alphabet of the language.

a) A->BC

b) A->a

c) S->e

d) All of the mentioned

### View Answer

### View Answer

Explanation: in CNF, the production rules are of the form:

A->BC

A-> a

S->e

S->aA

A->a

A->B

B-> A

B->bb

Which of the following is the production of B after simplification by removal of unit productions?

a) A

b) bb

c) aA

d) A| bb

### View Answer

### View Answer

Explanation: The simplified grammar can be presented as follows:

S->aA| aB

A->a

B-> bb

A-> x1x2x3…xn

put into P’ that production as well as all those generated by replacing null variables with e in all possible combinations. If all x(i) are nullable,

a) A->e is put into P’

b) A->e is not put into P’

c) e is a member of G’

d) None of the mentioned

### View Answer

### View Answer

Explanation: It is an exception that A->e is not put into P’ if all x(i) are nullable variables.

A-> a| aaA| abBc

B-> abba| b

a) A-> a| aaA| ababbAc| abbc

b) A-> a| aaA| ababbAc| abbc, B-> abba|b

c) A-> a| aaA| abbc, B->abba

d) None of the mentioned

### View Answer

### View Answer

Explanation: Using the substitution rules, we can simply eradicate what is useless and thus produce the simplified result i.e. A-> a| aaA| ababbAc| abbc.