Virtual Labs

Language acceptance by Deterministic Finite Automata (DFAs)

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

a: at least one Explanation

Explanation

b: at most one Explanation

Explanation

c: exactly one Explanation

Explanation

How many transition functions does a DFA have?

a: at least one Explanation

Explanation

b: at most 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

If a DFA accepts a string w, what must be true?

a: The string w must be empty Explanation

Explanation

b: The DFA must end in an accept state after processing w Explanation

Explanation

c: The DFA must visit every state while processing w Explanation

Explanation

d: The string w must have even length Explanation

Explanation

What is the language of a DFA?

a: The set of all states in the DFA Explanation

Explanation

b: The set of all strings that the DFA accepts Explanation

Explanation

c: The set of all transitions in the DFA Explanation

Explanation

d: The alphabet of the DFA 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 happens when a DFA reads the empty string ε?

a: The DFA rejects it automatically Explanation

Explanation

b: The DFA accepts it if the start state is an accept state Explanation

Explanation

c: The DFA enters an error state Explanation

Explanation

d: The DFA cannot process empty strings Explanation

Explanation

Given a DFA with n states, what is the maximum length of the shortest string that the DFA can accept?

a: n Explanation

Explanation

b: n - 1 Explanation

Explanation

c: 2n Explanation

Explanation

d: There is no maximum; it depends on the specific DFA Explanation

Explanation

If two DFAs M1 and M2 accept the same language, what can we say about them?

a: They must have the same number of states Explanation

Explanation

b: They must have identical transition functions Explanation

Explanation

c: They are equivalent DFAs Explanation

Explanation

d: They must have the same alphabet 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

Can a DFA accept an infinite language?

a: No, DFAs can only accept finite languages Explanation

Explanation

b: Yes, if the DFA has cycles and can reach an accept state from within a cycle Explanation

Explanation

c: Yes, but only if the DFA has infinite states Explanation

Explanation

d: No, because DFAs have finite memory Explanation

Explanation

In a DFA, what determines which state is reached after processing a string?

a: Only the length of the string Explanation

Explanation

b: Only the last symbol of the string Explanation

Explanation

c: The entire sequence of symbols in the string and the transition function Explanation

Explanation

d: The number of accept states in the DFA Explanation

Explanation