# Multiple choice question for engineering

## Set 1

1. Under which of the following operation, NFA is not closed?

a) Negation

b) Kleene

c) Concatenation

d) None of the mentioned

### View Answer

2. It is less complex to prove the closure properties over regular languages using

a) NFA

b) DFA

c) PDA

d) Can’t be said

### View Answer

3. Which of the following is an application of Finite Automaton?

a) Compiler Design

b) Grammar Parsers

c) Text Search

d) All of the mentioned

### View Answer

4. John is asked to make an automaton which accepts a given string for all the occurrence of ‘1001’ in it. How many number of transitions would John use such that, the string processing application works?

a) 9

b) 11

c) 12

d) 15

### View Answer

5. Which of the following do we use to form an NFA from a regular expression?

a) Subset Construction Method

b) Power Set Construction Method

c) Thompson Construction Method

d) Scott Construction Method

### View Answer

6. Which among the following can be an example of application of finite state machine(FSM)?

a) Communication Link

b) Adder

c) Stack

d) None of the mentioned

### View Answer

7. Which among the following is not an application of FSM?

a) Lexical Analyser

b) BOT

c) State charts

d) None of the mentioned

### View Answer

8. L1= {w | w does not contain the string tr }

L2= {w | w does contain the string tr}

Given ∑= {t, r}, The difference of the minimum number of states required to form L1 and L2?

a) 0

b) 1

c) 2

d) Cannot be said

### View Answer

9. Predict the number of transitions required to automate the following language using only 3 states:

L= {w | w ends with 00}

a) 3

b) 2

c) 4

d) Cannot be said

### View Answer

10. The total number of states to build the given language using DFA:

L= {w | w has exactly 2 a’s and at least 2 b’s}

a) 10

b) 11

c) 12

d) 13

### View Answer

## Set 2

1. Which of the following are related to construction of One Tape turing machines?

a) JFLAP

b) NFLAP

c) Both (a) and (b)

d) None of the mentioned

### View Answer

2. Which of the following topics cannot be covered using JFLAPS?

a) L-System

b) Unrestricted Grammar

c) Regular Expression

d) None of the mentioned

### View Answer

3. State true or false:

Statement: Multitape turing machine have multi tapes where each tape is accessed with one head.

a) true

b) false

### View Answer

4. Which of the following statements is/are true?

a) Every multitape turing machine has its equivalent single tape turing machine

b) Every multitape turing machine is an abstract machine

c) Both (a) and (b)

d) None of the mentioned

### View Answer

5. Are Multitape and Multitrack turing machines same?

a) Yes

b) No

c) Somewhat yes

d) Cannot tell

### View Answer

6. In a n-track turing machine, _________ head/heads read and write on all tracks simultaneously.

a) one

b) two

c) n

d) infinite

### View Answer

7. Which of the following does not exists?

a) Turing Machine with Multiple heads

b) Turing Machine with infinite tapes

c) Turing machine with two dimensional tapes

d) None of the mentioned

### View Answer

8. Can a multitape turing machine have an infinte number of tapes?

a) Yes

b) No

### View Answer

9. Every language accepted by a k-tape TM is _____ by a single-tape TM.

a) accepted

b) not accepted

c) generated

d) not generated

### View Answer

10. Which of the following is/are a basic TM equivalent to?

a) Multitrack TM

b) Multitape TM

c) Non-deterministic TM

d) All of the mentioned

### View Answer

## Set 3

1. The decision problem is the function from string to ______________

a) char

b) int

c) boolean

d) none of the mentioned

### View Answer

2. A language L is said to be ____________ if there is a turing machine M such that L(M)=L and M halts at every point.

a) Turing acceptable

b) decidable

c) undecidable

d) none of the mentioned

### View Answer

3. Which aong the following are undecidable theories?

a) The first order theory of boolean algebra

b) The first order theory of Euclidean geomentry

c) The first order theory of hyperbolic geometry

d) The first order theory of the natural number with addition, multiplication, and equality

### View Answer

4. Rec-DFA = {

Fill in the blank:

Rec-DFA is ___________

a) Undecidable

b) Decidable

c) Non finite

d) None of the mentioned

### View Answer

5. Which among the following are semi decidable?

a) Empty-DFA

b) Rec-NFA

c) Infinite-DFA

d) All of the mentioned

### View Answer

6. The language accepted by a turing machine is called ____________

a) Recursive Ennumerable

b) Recursive

c) Both (a) and (b)

d) None of the mentioned

### View Answer

7. Decidable can be taken as a synonym to:

a) recursive

b) non recursive

c) recognizable

d) none of the mentioned

### View Answer

8. The problems which have no algorithm, regardless of whether or not they are accepted by a turing machine that fails to halts on some input are referred as:

a) Decidable

b) Undecidable

c) Computable

d) None of the mentioned

### View Answer

9. An algorithm is called efficient if it runs in ____________ time on a serial computer.

a) polynomial

b) non polynomial

c) logarithmic

d) none of the mentioned

### View Answer

^{3}log2

^{n}) Runtimes of inefficient algorithms O(2

^{n}), O(n!)

10. A problem is called __________ if its has an efficient algorithm for itself.

a) tractable

b) intractable

c) computational

d) none of the mentioned

### View Answer

11. A formal language is recursive if :

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

12. Recursive languages are also known as:

a) decidable

b) undecidable

c) sometimes decidable

d) none of the mentioned

### View Answer

13. The class of recursive language is known as:

a) R

b) RC

c) RL

d) All of the mentioned

### View Answer

14. Which of the following was not a part of Chomsky hierarchy ?

a) Context sensitive grammar

b) Unrestricted grammar

c) Recursive grammar

d) None of the mentioned

### View Answer

## Set 4

1. The number of tuples in an extended Non Deterministic Finite Automaton:

a) 5

b) 6

c) 7

d) 4

### View Answer

2. Choose the correct option for the given statement:

Statement: The DFA shown represents all strings which has 1 at second last position.

a) Correct

b) Incorrect, Incomplete DFA

c) Wrong proposition

d) May be correct

### View Answer

3. What is wrong in the given definition?

Def: ({q0, q1, q2}, {0,1}, δ, q3, {q3})

a) The definition does not satisfy 5 Tuple definition of NFA

b) There are no transition definition

c) Initial and Final states do not belong to the Graph

d) Initial and final states can’t be same

### View Answer

4. If δ is the transition function for a given NFA, then we define the δ’ for the DFA accepting the same language would be:

Note: S is a subset of Q and a is a symbol.

a) δ’ (S, a) =U_{pϵs} δ (p, a)

b) δ’ (S, a) =U_{p≠s} δ (p, a)

c) δ’ (S, a) =U_{pϵs} δ(p)

d) δ’ (S) =U_{p≠s} δ(p)

### View Answer

5. What is the relation between DFA and NFA on the basis of computational power?

a) DFA > NFA

b) NFA > DFA

c) Equal

d) Can’t be said

### View Answer

6. If a string S is accepted by a finite state automaton, S=s_{1}s_{2}s_{3}……s_{n} where s_{i}ϵ∑ and there exists a sequence of states r0, r1, r2…… rn such that δ(r(i), s_{i+1}) =r_{i+1} for each 0, 1, …n-1, then r(n) is:

a) initial state

b) transition symbol

c) accepting state

d) intermediate state

### View Answer

7. According to the given table, compute the number of transitions with 1 as its symbol but not 0:

a) 4

b) 3

c) 2

d) 1

### View Answer

8. From the given table, δ*(q0, 011) =?

a) {q0}

b) {q1} U {q0, q1, q2}

c) {q2, q1}

d) {q3, q1, q2, q0}

### View Answer

_{rϵ}δ*(q0,01) δ (r, 1) = {q0, q1, q2}.

9. Number of times the state q3 or q2 is being a part of extended 6 transition state is

a) 6

b) 5

c) 4

d) 7

### View Answer

10. Predict the missing procedure:

1.Δ(Q0, ε) ={Q0},

2.Δ(Q0, 01) = {Q0, Q1}

3.δ(Q0, 010) =?

a) {Q0, Q1, Q2}

b) {Q0, Q1}

c) {Q0, Q2}

d) {Q1, Q2}

### View Answer

## Set 5

1. Assume the R is a relation on a set A, aRb is partially ordered such that a and b are _____________

a) reflexive

b) transitive

c) symmetric

d) reflexive and transitive

### View Answer

2. The non- Kleene Star operation accepts the following string of finite length over set A = {0,1} | where string s contains even number of 0 and 1

a) 01,0011,010101

b) 0011,11001100

c) ε,0011,11001100

d) ε,0011,11001100

### View Answer

3. A regular language over an alphabet ∑ is one that cannot be obtained from the basic languages using the operation

a) Union

b) Concatenation

c) Kleene*

d) All of the mentioned

### View Answer

4. Statement 1: A Finite automata can be represented graphically; Statement 2: The nodes can be its states; Statement 3: The edges or arcs can be used for transitions

Hint: Nodes and Edges are for trees and forests too.

Which of the following make the correct combination?

a) Statement 1 is false but Statement 2 and 3 are correct

b) Statement 1 and 2 are correct while 3 is wrong

c) None of the mentioned statements are correct

d) All of the mentioned

### View Answer

5. The minimum number of states required to recognize an octal number divisible by 3 are/is

a) 1

b) 3

c) 5

d) 7

### View Answer

6. Which of the following is a not a part of 5-tuple finite automata?

a) Input alphabet

b) Transition function

c) Initial State

d) Output Alphabet

### View Answer

7. If an Infinite language is passed to Machine M, the subsidiary which gives a finite solution to the infinite input tape is ______________

a) Compiler

b) Interpreter

c) Loader and Linkers

d) None of the mentioned

### View Answer

8. The number of elements in the set for the Language L={xϵ(∑r) *|length if x is at most 2} and ∑={0,1} is_________

a) 7

b) 6

c) 8

d) 5

### View Answer

9. For the following change of state in FA, which of the following codes is an incorrect option?

a) δ (m, 1) =n

b) δ (0, n) =m

c) δ (m,0) =ε

d) s: accept = false; cin >> char;

if char = “0” goto n;

### View Answer

10. Given: ∑= {a, b}

L= {xϵ∑*|x is a string combination}

∑4 represents which among the following?

a) {aa, ab, ba, bb}

b) {aaaa, abab, ε, abaa, aabb}

c) {aaa, aab, aba, bbb}

d) All of the mentioned