# Automata Theory Multiple Choice Question & Answers (MCQs) set-3

1. Moore Machine is an application of:

a) Finite automata without input

b) Finite automata with output

c) Non- Finite automata with output

d) None of the mentioned

### View Answer

Explanation: Finite automaton with an output is categorize din two parts: Moore M/C and Mealy M/C.

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) e,0011,11001100

d) e,0011,11001100

### View Answer

Answer: b

Explanation: The Kleene star of A, denoted by A*, is the set of all strings obtained by concatenating zero or more strings from A.

3. A DFA cannot be represented in the following format

a) Transition graph

b) Transition Table

c) C code

d) None of the mentioned

### View Answer

Explanation: A DFA can be represented in the following formats: Transition Graph, Transition Table, Transition tree/forest/Any programming Language.

4.Predict the following step in the given bunch of steps which accepts a strings which is of even length and has a prefix=’01’

d (q0, e) =q0 < d(q0,0) =d (d (q0, e),0) =d(q0,0) =q1 < _______________

a) d (q0, 011) =d (d (q0,1), 1) =d (q2, 1) =q3

b) d (q0, 01) =d (d (q0, 0), 1) = d (q1, 1) =q2

c) d (q0, 011) =d (d (q01, 1), 1) =d (q2, 0) =q3

d) d (q0, 0111) =d (d (q0, 011), 0) = d (q3, 1) =q2

### View Answer

Explanation: Here, d refers to transition function and results into new state or function when an transition is performed over its state.

5. d*(q,ya) is equivalent to .

a) d((q,y),a)

b) d(d*(q,y),a)

c) d(q,ya)

d) independent from d notation

### View Answer

Explanation: First it parse y string after that it parse a.

6. Which of the following is correct proposition?

Statement 1: Non determinism is a generalization of Determinism.

Statement 2: Every DFA is automatically an NFA

a) Statement 1 is correct because Statement 2 is correct

b) Statement 2 is correct because Statement 2 is correct

c) Statement 2 is false and Statement 1 is false

d) Statement 1 is false because Statement 2 is false

### View Answer

Answer: b

Explanation: DFA is a specific case of NFA.

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

Explanation: We can represent one language in more one FSMs, example for a same language we have a DFA and an equivalent NFA.

8. Which of the following options is correct for the given statement?

Statement: If K is the number of states in NFA, the DFA simulating the same language would have states less than 2k.

a) True

b) False

### View Answer

Explanation: If K is the number of states in NFA, the DFA simulating the same language would have states equal to or less than 2k.

9. Let N (Q, ?, d, q0, A) be the NFA recognizing a language L. Then for a DFA (Q’, ?, d’, q0’, A’), which among the following is true?

a) Q’ = P(Q)

b) ?’ = d’ (R, a) = {q ? Q | q ? d (r, a), for some r ? R}

c) Q’={q0}

d) All of the mentioned

### View Answer

Explanation: All the optioned mentioned are the instruction formats of how to convert a NFA to a DFA.

10. e-transitions are

a) conditional

b) unconditional

c) input dependent

d) none of the mentioned

### View Answer

Explanation: An epsilon move is a transition from one state to another that doesnt require any specific condition.

11. According to the precedence rules, x-y-z is equivalent to which of the following?

a) (x-y)-z

b) x-(y-z)

c) Both (x-y)-z and x-(y-z)

d) None of the mentioned

### View Answer

Explanation: In arithmetic, we group two of the same operators from the left, hence x-y-z is equivalent to (x-y)-z and not x-(y—z).

12. ____________ is used for grouping up of characters into token.

a) Lexical Analyzer

b) oolex

c) jflex

d) All of the mentioned

### View Answer

Explanation: oolex, flex, lex, jflex, all are lexical analyzer tools which perform the following function.

13. The minimum number of 1’s to be used in a regular expression of the given language:

R(x): The language of all strings containing exactly 2 zeroes.

a) 2

b) 3

c) 0

d) 1

### View Answer

Explanation: It is not required to automate the question if asked theoretically.The number of zeroes fixed is 2. Therefore, we can represent the regular expression as 1*01*01*.

14. a ^ nb ^ m where n >= 1, m >= 1, nm >= 3 is example of

a) Type 0

b) Type 1

c) Type 2

d) Type 3

### View Answer

Explanation: It is a regular expression.

15. Complement of (a + b)* will be

a) phi

b) null

c) a

d) b

### View Answer

Explanation: Given expression accept all string so complement will accept nothing.