# Multiple choice question for engineering

## Set 1

1. A finite automaton accepts which type of language:

a) Type 0

b) Type 1

c) Type 2

d) Type 3

### View Answer

2. Which among the following are incorrect regular identities?

a) εR=R

b) ε*=ε

c) Ф*=ε

d) RФ=R

### View Answer

3. Simplify the following regular expression:

ε+1*(011) *(1*(011) *) *

a) (1+011) *

b) (1*(011) *)

c) (1+(011) *) *

d) (1011) *

### View Answer

4. P, O, R be regular expression over ∑, P is not ε, then

R=Q + RP has a unique solution:

a) Q*P

b) QP*

c) Q*P*

d) (P*O*) *

### View Answer

5. Arden’s theorem is true for:

a) More than one initial states

b) Null transitions

c) Non-null transitions

d) None of the mentioned

### View Answer

6. The difference between number of states with regular expression (a + b) and (a + b) * is:

a) 1

b) 2

c) 3

d) 0

### View Answer

7. In order to represent a regular expression, the first step to create the transition diagram is:

a) Create the NFA using Null moves

b) Null moves are not acceptable, thus should not be used

c) Predict the number of states to be used in order to construct the Regular expression

d) None of the mentioned

### View Answer

8. (0+ε) (1+ε) represents

a) {0, 1, 01, ε}

b) {0, 1, ε}

c) {0, 1, 01 ,11, 00, 10, ε}

d) {0, 1}

### View Answer

9. The minimum number of states required to automate the following Regular Expression:

(1) *(01+10) (1) *

a) 4

b) 3

c) 2

d) 5

### View Answer

10. Regular Expression denote precisely the ________ of Regular Language.

a) Class

b) Power Set

c) Super Set

d) None of the mentioned

### View Answer

## Set 2

1. If two sets, R and T has no elements in common i.e. RÇT=Æ, then the sets are called

a) Complement

b) Union

c) Disjoint

d) Connected

### View Answer

2. Which among the following is not a part of the Context free grammar tuple?

a) End symbol

b) Start symbol

c) Variable

d) Production

### View Answer

3. A context free grammar is a ___________

a) English grammar

b) Regular grammar

c) Context sensitive grammar

d) None of the mentioned

### View Answer

4. The closure property of context free grammar includes :

a) Kleene

b) Concatenation

c) Union

d) All of the mentioned

### View Answer

5. Which of the following automata takes stack as auxiliary storage?

a) Finite automata

b) Push down automata

c) Turing machine

d) All of the mentioned

### View Answer

6. Which of the following automata takes queue as an auxiliary storage?

a) Finite automata

b) Push down automata

c) Turing machine

d) All of the mentioned

### View Answer

7. A context free grammar can be recognized by

a) Push down automata

b) 2 way linearly bounded automata

c) Both (a) and (b)

d) None of the mentioned

### View Answer

8. A null production can be referred to as:

a) String

b) Symbol

c) Word

d) All of the mentioned

### View Answer

9. The context free grammar which generates a Regular Language is termed as:

a) Context Regular Grammar

b) Regular Grammar

c) Context Sensitive Grammar

d) None of the mentioned

### View Answer

10. NPDA stands for

a) Non-Deterministic Push Down Automata

b) Null-Push Down Automata

c) Nested Push Down Automata

d) All of the mentioned

### View Answer

## Set 3

1. All set of polynomial questions which can be solved by a turing machine using a polynomial amount of space:

a) PSPACE

b) NPSPACE

c) EXPSPACE

d) None of the mentioned

### View Answer

2. PSPACE is strictly the super set of:

a) Regular language

b) Context free language

c) Context Sensitive Language

d) None of the mentioned

### View Answer

3. Savitch theorem relates to which of the following:

a) PSPACE=NPSPACE

b) Alternating Turing Machine

c) Time complexity

d) None of the mentioned

### View Answer

4. The class PSPACE is closed under the following operations:

a) Union

b) Concatenation

c) Kleene

d) All of the mentioned

### View Answer

5. Correct the given order:

NL∈ P∈ NP∈ PH∈ PSPACE

a) NP∈ P∈ NL∈ PH∈ PSPACE

b) NL∈ PH∈ NP∈ P∈ PSPACE

c) NL∈ P∈ NP∈ PH∈ PSPACE

d) None of the mentioned

### View Answer

6. NL ∈ PSPACE ∈ EXPSPACE

The given relation involves which of the following theorems?

a) Space hierarchy theorem

b) Savitch’s theorem

c) Both (a) and (b)

d) None of the mentioned

### View Answer

7. Statement : All PSPACE problems can be reduced to PSPACE-complete problems.

State true or false:

a) true

b) false

### View Answer

8. Without needing extra __________ we can simulate non deterministic turing machine using deterministic turing machine.

a) time

b) space

c) both time and space

d) none of the mentioned

### View Answer

9. Complement of all the problems in PSPACE is ________

a) PSPACE

b) NL

c) P

d) All of the mentioned

### View Answer

10. Which of the following PSPACE can be characterized into?

a) APTIME

b) AP

c) Quantom complexity class

d) None of the mentioned

### View Answer

## Set 4

1. A turing machine has ____________ number of states in a CPU.

a) finite

b) infinte

c) May be finite

d) None of the mentioned

### View Answer

2. Suppose we have a simple computer with control unit holding a PC with a 32 bit address + Arithmetic unit holding one double length 64 bit Arithmetic Register. The number of states the finite machine will hold:

a) 2^{(32*64)}

b) 2^{96}

c) 96

d) 32

### View Answer

3. In one move a turing machine will:

a) Change a state

b) Write a tape symbol in the cell scanned

c) Move the tape head left or right

d) All of the mentioned

### View Answer

4. State true or false:

Statement: We can use the finite control of turing machine to hold a finite amount of data.

a) true

b) false

### View Answer

5. Statement 1: Multitrack Turing machine.

Statement 2: Gamma is Cartesian product of a finite number of finite sets.

Which among the following is the correct option?

a) Statement 1 is the assertion and Statement 2 is the reason

b) Statement 1 is the reason and Statement 2 is the assertion

c) Statement 1 and Statement 2 are independent from each other

d) None of the mentioned

### View Answer

6. A multi track turing machine can described as a 6-tuple (Q, X, S, d, q0, F) where X represents:

a) input alphabet

b) tape alphabet

c) shift symbols

d) none of the mentioned

### View Answer

7. Which of the following statements are false?

a) A multi track turing machine is a special kind of multi tape turing machine

b) 4-heads move independently along 4-tracks in standard 4-tape turing machine

c) In a n-track turing machine, n head reads and writes on all the tracks simultaneously.

d) All of the mentioned

### View Answer

8. State true or false:

Statement: Two track turing machine is equivalent to a standard turing machine.

a) true

b) false

### View Answer

9. Which of the following is/are not true for recursively ennumerable language?

a) partially decidable

b) Turing acceptable

c) Turing Recognizable

d) None of the mentioned

### View Answer

10. According to Chomsky hierarchy, which of the following is adopted by Recursively Ennumerable language?

a) Type 0

b) Type 1

c) Type 2

d) Type 3

### View Answer

## Set 5

1. Relate the following statement:

Statement: All sufficiently long words in a regular language can have a middle section of words repeated a number of times to produce a new word which also lies within the same language.

a) Turing Machine

b) Pumping Lemma

c) Arden’s theorem

d) None of the mentioned

### View Answer

2. While applying Pumping lemma over a language, we consider a string w that belong to L and fragment it into _________ parts.

a) 2

b) 5

c) 3

d) 6

### View Answer

3. If we select a string w such that w∈L, and w=xyz. Which of the following portions cannot be an empty string?

a) x

b) y

c) z

d) all of the mentioned

### View Answer

4. Let w= xyz and y refers to the middle portion and |y|>0.What do we call the process of repeating y 0 or more times before checking that they still belong to the language L or not?

a) Generating

b) Pumping

c) Producing

d) None of the mentioned

### View Answer

5. There exists a language L. We define a string w such that w∈L and w=xyz and |w| >=n for some constant integer n.What can be the maximum length of the substring xy i.e. |xy|<=?

a) n

b) |y|

c) |x|

d) none of the mentioned

### View Answer

6. Fill in the blank in terms of p, where p is the maximum string length in L.

Statement: Finite languages trivially satisfy the pumping lemma by having n = ______

a) p*1

b) p+1

c) p-1

d) None of the mentioned

### View Answer

7. Answer in accordance to the third and last statement in pumping lemma:

For all _______ xy^{i}z ∈L

a) i>0

b) i<0

c) i<=0

d) i>=0

### View Answer

^{m}w ∈L.

8. If d is a final state, which of the following is correct according to the given diagram?

a) x=p, y=qr, z=s

b) x=p, z=qrs

c) x=pr, y=r, z=s

d) All of the mentioned

### View Answer

9. Let w be a string and fragmented by three variable x, y, and z as per pumping lemma. What does these variables represent?

a) string count

b) string

c) both (a) and (b)

d) none of the mentioned

### View Answer

10. Which of the following one can relate to the given statement:

Statement: If n items are put into m containers, with n>m, then atleast one container must contain more than one item.

a) Pumping lemma

b) Pigeon Hole principle

c) Count principle

d) None of the mentioned