# Multiple choice question for engineering

## Set 1

1. Language classes have the following property:

a) Closure property

b) Decision property

c) Closure & Decision property

d) None of the mentioned

### View Answer

2. Which of the following are decision properties?

a) Emptiness

b) Infiniteness

c) Membership

d) All of the mentioned

### View Answer

3. Pick the odd one out of the given properties of a regular language:

a) Kleene

b) Reversal

c) Homomorphism

d) Membership

### View Answer

4. For an automata, which of the following are equivalent variants?

DFA,NFA and NFA with epsilon transitions

a) DFA and NFA

b) NFA and epsilon NFA

c) DFA and epsilon NFA

d) All of the mentioned

### View Answer

5. Which of the following are not meant to specify a regular language?

a) Regular Expression

b) DFA

c) NDFA and epsilon-NFA

d) All of the mentioned

### View Answer

6. Which of the following problems do not belong to decision properties?

a) Given two languages, are there strings that are in both

b) Is the language a subset of another regular language

c) Is the language same as another regular language

d) None of the mentioned

### View Answer

7. Which of the following is a function of Closure properties?

a) Helps construct representations

b) Helps show informally described languages not to be in class

c) Both (a) and (b)

d) None of the mentioned

### View Answer

8. Suppose there is a string w=abbab, and there exists a DFA which accepts w. How many stepts will be required to test its membership?

a) 2

b) 1

c) 4

d) None of the mentioned

### View Answer

9. If a DFA has n states and the language contains any string of length n or more, the language is termed as:

a) Infinite

b) Empty

c) Non regular

d) None of the mentioned

### View Answer

10. State true or false:

Statement: If an n-state DFA accepts a string w of length n or more, then there must be a state that appears twice on the path labeled w from the start state to the final state.

a) true

b) false

### View Answer

## Set 2

1. Which of the following technique is used to find whether a natural language isnt recursive ennumerable?

a) Diagonalization

b) Recursive Induction

c) Both (a) and (b)

d) None of the mentioned

### View Answer

2. Diagonalization can be useful in:

a) To find a non recursively ennumerable language

b) To prove undecidablility of haltig problem

c) Both (a) and (b)

d) None of the mentioned

### View Answer

3. Which of the following are undecidable problems?

a) Determining whether two grammars generate the same language

b) Determining whether a grammar is ambiguous

c) Both (a) and (b)

d) None of the mentioned

### View Answer

4. Which of the following are incorrect options?

a) Informally, problem is a yes/no question about an infinite set of possible instances

b) Formally, a problem is a language

c) Both (a) and (b)

d) None of the mentioned

### View Answer

5. If a problem has an algorithm to answer it, we call it _________

a) decidable

b) solved

c) recognizable

d) none of the mentioned

### View Answer

6. Which of the following are decidable problems?

a) Can a particular line of code in a program ever be executed?

b) Do two given CFG’s generate the same language

c) Is a given CFG ambiguous?

d) None of the mentioned

### View Answer

7.Which one of the following is true for the given?

A={(M,w)|M is a turing machine that accepts string w}

a) A concrete undecidable problem

b) A is recognizable but not decidable

c) -A is not recognizable

d) All of the mentioned

### View Answer

8. Which of the following are correct statements?

a) TMs that always halt are known as Decidable problems

b) TMs that are guaranteed to halt only on acceptance are recursive ennumerable.

c) Both (a) and (b)

d) None of the mentioned

### View Answer

9. Statement: If L id R.E., L^{c} needs to be R.E. Is it correct?

a) Yes

b) No

c) Maybe

d) Cannot predict

### View Answer

10. Which of the following is true for The Halting problem?

a) It is recursively ennumerable

b) It is undecidable

c) Both (a) and (b)

d) None of the mentioned

### View Answer

11. With reference to binary strings, state true or false:

Statement: For any turing machine, the input alphabet is restricted to {0,1}.

a) true

b) false

### View Answer

12. With reference ti enumeration of binary strings, the conversion of binary strings to integer is possible by treating the resulting string as a base ____ integer.

a) 2

b) 8

c) 16

d) All of the mentioned

### View Answer

## Set 3

1. How many languages are over the alphabet R?

a) countably infinite

b) countably finite

c) uncountable finite

d) uncountable infinite

### View Answer

2. According to the 5-tuple representation i.e. FA= {Q, ∑, δ, q, F}

Statement 1: q ϵ Q’; Statement 2: FϵQ

a) Statement 1 is true, Statement 2 is false

b) Statement 1 is false, Statement 2 is true

c) Statement 1 is false, Statement 2 may be true

d) Statement 1 may be true, Statement 2 is false

### View Answer

3. δˆ tells us the best:

a) how the DFA S behaves on a word u

b) the state is the dumping state

c) the final state has been reached

d) Kleene operation is performed on the set

### View Answer

4. Which of the following option is correct?

A= {{abc, aaba}. {ε, a, bb}}

a) abcbb ₵ A

b) ε₵A

c) ε may not belong to A

d) abca ₵ A

### View Answer

5. For a DFA accepting binary numbers whose decimal equivalent is divisible by 4, what are all the possible remainders?

a) 0

b) 0,2

c) 0,2,4

d) 0,1,2,3

### View Answer

6. Which of the following x is accepted by the given DFA (x is a binary string ∑= {0,1})?

a) divisible by 3

b) divisible by 2

c) divisible by 2 and 3

d) divisible by 3 and 2

### View Answer

7. Given:

L1= {xϵ ∑*|x contains even no’s of 0’s}

L2= {xϵ ∑*|x contains odd no’s of 1’s}

No of final states in Language L1 U L2?

a) 1

b) 2

c) 3

d) 4

### View Answer

8. The maximum number of transition which can be performed over a state in a DFA?

∑= {a, b, c}

a) 1

b) 2

c) 3

d) 4

### View Answer

9. The maximum sum of in degree and out degree over a state in a DFA can be determined as:

∑= {a, b, c, d}

a) 4+4

b) 4+16

c) 4+0

d) depends on the Language

### View Answer

10. The sum of minimum and maximum number of final states for a DFA n states is equal to:

a) n+1

b) n

c) n-1

d) n+2

### View Answer

## Set 4

1. Subset Construction method refers to:

a) Conversion of NFA to DFA

b) DFA minimization

c) Eliminating Null references

d) ε-NFA to NFA

### View Answer

2. Given Language:

L_{n}= {xϵ {0,1} * | |x|≥n, nth symbol from the right in x is 1}

How many state are required to execute L_{3} using NFA?

a) 16

b) 15

c) 8

d) 7

### View Answer

3. Which of the following does the given NFA represent?

a) {11, 101} * {01}

b) {110, 01} * {11}

c) {11, 110} * {0}

d) {00, 110} * {1}

### View Answer

4. The number of transitions required to convert the following into equivalents DFA:

a) 2

b) 3

c) 1

d) 0

### View Answer

5. If L is a regular language, L^{c} and L^{r} both will be:

a) Accepted by NFA

b) Rejected by NFA

c) One of them will be accepted

d) Cannot be said

### View Answer

^{c}and L

^{r}both are regular even.

6. In NFA, this very state is like dead-end non final state:

a) ACCEPT

b) REJECT

c) DISTINCT

d) START

### View Answer

7. We can represent one language in more one FSMs, true or false?

a) TRUE

b) FALSE

c) May be true

d) Cannot be said

### View Answer

8. The production of form non-terminal -> ε is called:

a) Sigma Production

b) Null Production

c) Epsilon Production

d) All of the mentioned

### View Answer

9. Which of the following is a regular language?

a) String whose length is a sequence of prime numbers

b) String with substring ww^{r} in between

c) Palindrome string

d) String with even number of Zero’s

### View Answer

10. Which of the following recognizes the same formal language as of DFA and NFA?

a) Power set Construction

b) Subset Construction

c) Robin-Scott Construction

d) All of the mentioned

### View Answer

## Set 5

1. A turing machine that is able to simulate other turing machines:

a) Nested Turing machines

b) Universal Turing machine

c) Counter machine

d) None of the mentioned

### View Answer

2. Which of the problems are unsolvable?

a) Halting problem

b) Boolean Satisfiability problem

c) Both (a) and (b)

d) None of the mentioned

### View Answer

3. Which of the following a turing machine does not consist of?

a) input tape

b) head

c) state register

d) none of the mentioned

### View Answer

4. The value of n if turing machine is defined using n-tuples:

a) 6

b) 7

c) 8

d) 5

### View Answer

5. If d is not defined on the current state and the current tape symbol, then the machine ______

a) does not halts

b) halts

c) goes into loop forever

d) none of the mentioned

### View Answer

_{A}or h

_{R}, we say TM halts. Once it has halted, it cannot move further, since d is not defined at any pair (h

_{A},X) or (h

_{R},X) where h

_{A}= accept halting state and h

_{R}= reject halting state.

6. Statement: Instantaneous descriptions can be designed for a Turing machine.

State true or false:

a) true

b) false

### View Answer

7. Which of the following are the models equivalent to Turing machine?

a) Multi tape turing machine

b) Multi track turing machine

c) Register machine

d) All of the mentioned

### View Answer

8. Which among the following is incorrect for o-machines?

a) Oracle Turing machines

b) Can be used to study decision problems

c) Visualizes Turing machine with a black box which is able to decide cerain decion problems in one operation

d) None of the mentioned

### View Answer

9. RASP stands for:

a) Random access storage program

b) Random access stored program

c) Randomly accessed stored program

d) Random access storage programming

### View Answer

10. Which of the following is not true about RASP?

a) Binary search can be performed more quickly using RASP than a turing machine

b) Stores its program in memory external to its state machines instructions

c) Has infinite number of distinguishable, unbounded registers

d) Binary search can be performed less quickly using RASP than a turing machine

e) More than two options are incorrect

### View Answer

11. State true or false:

Statement: RASP is to RAM like UTM is to turing machine.

a) true

b) false