Virtual Labs

Language acceptance by Deterministic Finite Automata (DFAs)

How many states can the automaton transition to upon reading input?

a: atleast one Explanation

Explanation

b: atmost one Explanation

Explanation

c: exactly one Explanation

Explanation

How many transition functions does a DFA have?

a: atleast one Explanation

Explanation

b: atmost one Explanation

Explanation

c: exactly one Explanation

Explanation

Can a DFA run infinitely?

a: yes Explanation

Explanation

b: no Explanation

Explanation

c: depends on transition function Explanation

Explanation

d: depends on input Explanation

Explanation

Can a DFA be constructed to count the parity of a given input symbol?

a: yes in all cases Explanation

Explanation

b: yes if alphabet set is binary Explanation

Explanation

c: no Explanation

Explanation

What is the pumping lemma for regular languages used for?

a: To prove that a language is regular Explanation

Explanation

b: To prove that a language is not regular Explanation

Explanation

c: To minimize the number of states in a DFA Explanation

Explanation

d: To convert NFAs to DFAs Explanation

Explanation

Which of the following operations is closed under regular languages?

a: Union only Explanation

Explanation

b: Intersection only Explanation

Explanation

c: Complement only Explanation

Explanation

d: Union, intersection, and complement Explanation

Explanation

What is the minimum number of states required for a DFA that accepts strings over {0,1} with an even number of 0s and an odd number of 1s?

a: 2 states Explanation

Explanation

b: 3 states Explanation

Explanation

c: 4 states Explanation

Explanation

d: 5 states Explanation

Explanation

What is DFA minimization?

a: Reducing the size of the input alphabet Explanation

Explanation

b: Creating an equivalent DFA with the minimum number of states Explanation

Explanation

c: Removing unreachable states only Explanation

Explanation

d: Converting a DFA to an NFA Explanation

Explanation

Two states in a DFA are equivalent if:

a: They have the same number of outgoing transitions Explanation

Explanation

b: They are both accept states or both non-accept states Explanation

Explanation

c: For every possible input string, they lead to the same acceptance outcome Explanation

Explanation

d: They have the same label Explanation

Explanation

What is the time complexity of the standard DFA minimization algorithm?

a: O(n) Explanation

Explanation

b: O(n log n) Explanation

Explanation

c: O(n²) Explanation

Explanation

d: O(n³) Explanation

Explanation

Which of the following languages is NOT regular?

a: Strings over {0,1} with equal number of 0s and 1s Explanation

Explanation

b: Strings over {0,1} ending with 01 Explanation

Explanation

c: Strings over {0,1} with even length Explanation

Explanation

d: Strings over {0,1} containing the substring 101 Explanation

Explanation

What is the relationship between DFAs and regular expressions?

a: DFAs are more powerful than regular expressions Explanation

Explanation

b: Regular expressions are more powerful than DFAs Explanation

Explanation

c: DFAs and regular expressions have equivalent expressive power Explanation

Explanation

d: DFAs and regular expressions are incomparable Explanation

Explanation

In practical applications, what is a major advantage of DFAs over NFAs?

a: DFAs can recognize more languages than NFAs Explanation

Explanation

b: DFAs are easier to construct than NFAs Explanation

Explanation

c: DFAs have faster execution time for string matching Explanation

Explanation

d: DFAs require less memory than NFAs Explanation

Explanation