Non Deterministic Finite Automata Questions

MCQ bookmark_border

1.

a(bab)*?a(ba

 

A

B

C

D

None of the mentioned

Correct Answer: A

We can verify that the string ababa is accepted by this NFA once we

Check Answer report_problem Report forum Discussion

MCQ bookmark_border

2.

Which is the correct NDFA for the following mentioned expression?

(ab)*?(aba)*

A

B

C

D

None of the mentioned

Correct Answer: B

A ? transition takes no input and represents a pure nondeterministic choice of being in the state or the target state without having done any processing.

Check Answer report_problem Report forum Discussion

MCQ bookmark_border

3.

NDFAs where introduced by ____________

A

Michael O Rabin & Dana Scott

B

Dan Brown

C

Sun micro system Labs

D

SAP Labs

Correct Answer: A

NFAs were introduced Dana Scott and Michael O. Rabin who also showed their equivalence to DFAs.

Check Answer report_problem Report forum Discussion

MCQ bookmark_border

4.

The regular languages are not closed under ___________

A

Concatenation

B

Union

C

Kleene star

D

Complement

Correct Answer: D

RE are closed under Union (cf. picture) Intersection Concatenation Negation Kleene closure.

Check Answer report_problem Report forum Discussion

MCQ bookmark_border

5.

The Tuples for NDFA is ___________

A

?, Q, q0, F, ?

B

Q, q0, F, ?

C

?, Q, q0, F,?

D

F, Q, ?, q0, ?

Correct Answer: A

An NFA is represented formally by a 5-tuple, (Q, ?, ?, q0, F), of a set of states Q a set of input symbols ? a transition function ? : Q

Check Answer report_problem Report forum Discussion

MCQ bookmark_border

6.

NFAs are ________ DFAs.

A

Larger than

B

More expressive than

C

Less expressive than

D

Equally expressive as

Correct Answer: A

Because there is more number of states for an NDFA than for a DFA for a given expression.

Check Answer report_problem Report forum Discussion

MCQ bookmark_border

7.

An NFA

A

A Boolean value

B

A state

C

A set of states

D

An edge

Correct Answer: C

A transition function ?: Q

Check Answer report_problem Report forum Discussion

MCQ bookmark_border

8.

Which NDFA correctly represents the following RE?

a(bab)*?a(ba)* 

A

B

C

D

None of the mentioned

Correct Answer: A

A ? transition takes no input and represents a pure nondeterministic choice of being in the state or the target state without having done any processing.

Check Answer report_problem Report forum Discussion

MCQ bookmark_border

9.

A ? transition takes no input and represents a pure nondeterministic choice of being in the state or the target state without having done any processing.

A

Michael O Rabin & Dana Scott

B

Dan Brown

C

Sun micro system Labs

D

SAP Labs

Correct Answer: A

NFAs were introduced Dana Scott and Michael O. Rabin who also showed their equivalence to DFAs.

Check Answer report_problem Report forum Discussion

MCQ bookmark_border

10.

The regular languages are not closed under ___________

A

Concatenation

B

Union

C

Kleene star

D

Complement

Correct Answer: D

RE are closed under Union (cf. picture) Intersection Concatenation Negation Kleene closure.

Check Answer report_problem Report forum Discussion