Virtual Labs

Converting a Non-deterministic Finite Automaton to a Deterministic Finite Automaton

Which of the following statements is true for DFA and NFA?

a: DFA can have epsilon transitions, NFA cannot Explanation

Explanation

b: Every NFA has an equivalent DFA Explanation

Explanation

c: NFA is more powerful than DFA Explanation

Explanation

d: DFA is more powerful than NFA Explanation

Explanation

In a DFA, for each state, there are:

a: No transitions Explanation

Explanation

b: Exactly one transition for each symbol in the alphabet Explanation

Explanation

c: Multiple transitions for the same symbol Explanation

Explanation

d: At least one epsilon transition Explanation

Explanation

Which of the following is NOT a valid property of DFA?

a: It has a single initial state Explanation

Explanation

b: It can have multiple final states Explanation

Explanation

c: It allows epsilon transitions Explanation

Explanation

d: Every transition is uniquely determined by a symbol Explanation

Explanation

What is the time complexity of simulating a string of length 'n' on a DFA?

a: O(

n^2

) Explanation

Explanation

b: O(log n) Explanation

Explanation

c: O(1) Explanation

Explanation

d: O(n) Explanation

Explanation

Which of the following best describes the relationship between regular expressions, DFAs, and NFAs?

a: Regular expressions are more powerful than DFAs Explanation

Explanation

b: DFAs are more powerful than NFAs Explanation

Explanation

c: Regular expressions, DFAs, and NFAs are equivalent in power Explanation

Explanation

d: DFAs are equivalent to context-free grammars Explanation

Explanation

Which of the following is true about epsilon transitions in NFA?

a: They allow the NFA to change state without reading any input symbol Explanation

Explanation

b: They are used to decrease the number of states in DFA Explanation

Explanation

c: They make NFA more powerful than DFA Explanation

Explanation

d: They are not allowed in NFA Explanation

Explanation

Which of these operations can be efficiently performed by constructing a DFA for the language?

a: Concatenation Explanation

Explanation

b: Union Explanation

Explanation

c: Membership testing Explanation

Explanation

d: Reversal Explanation

Explanation

A language is said to be regular if it can be recognized by a:

a: Pushdown Automaton Explanation

Explanation

b: Context-Free Grammar Explanation

Explanation

c: Turing Machine Explanation

Explanation

d: Deterministic Finite Automaton Explanation

Explanation

Given two states p and q in a DFA, which of the following conditions implies they are equivalent?

a: p and q are both initial states Explanation

Explanation

b: p and q are final states Explanation

Explanation

c: For every input string, p and q transition to the same states Explanation

Explanation

d: There is a path from p to q and vice versa Explanation

Explanation

What is the main difference between a DFA and an NFA?

a: DFA has a unique transition for each input symbol in a given state, while NFA may have multiple transitions Explanation

Explanation

b: NFA requires more states than DFA Explanation

Explanation

c: DFA is used for non-regular languages, while NFA is used for regular languages Explanation

Explanation

d: DFA can simulate a Turing Machine Explanation

Explanation