CMSC330-10/15

CMSC 330 — Fall 2026 · October 15, 2026 · 179 players · Max 10 pts

Questions & Results

Q1 of 10Multiple ChoiceAccuracy45s · 1 pt

Which statement comparing DFAs and NFAs is true?

A NFAs can recognize some languages that no DFA can recognize
5
B A DFA may have ε-transitions
2
C In a DFA, a state may have two transitions on the same symbol
9
D Every NFA has an equivalent DFA that accepts the same language
128
✓ Correct
144 / 179 answered · 89% correct
Q2 of 10Multiple ChoiceAccuracy45s · 1 pt

When does an NFA accept an input string?

A When every possible path ends in an accepting state
1
B When at least one path consumes the whole string and ends in an accepting state
154
✓ Correct
C When some path passes through an accepting state at any point
4
D When exactly one path ends in an accepting state
4
163 / 179 answered · 94% correct
Q3 of 10Multiple ChoiceAccuracy75s · 1 pt

Consider this NFA over {a, b}. Missing transitions go to a dead state.

     a,b
     ┌─┐
     ▼ │
──► (0)┘──a──► (1) ──b──► ((2))

──► marks the start state; ((n)) is accepting.

Which string does it accept?

A ba
3
B abba
2
C aab
163
✓ Correct
D abb
2
170 / 179 answered · 96% correct
Q4 of 10Multiple ChoiceAccuracy75s · 1 pt

Consider this NFA over {a, b}. Missing transitions go to a dead state.

     a,b
     ┌─┐
     ▼ │
──► (0)┘──a──► (1) ──b──► ((2))

──► marks the start state; ((n)) is accepting.

Starting in state 0, which set of states is the NFA in after reading ab?

A {0, 2}
163
✓ Correct
B {2}
2
C {0, 1}
1
D {0, 1, 2}
9
175 / 179 answered · 93% correct
Q5 of 10Multiple ChoiceAccuracy45s · 1 pt

What is the ε-closure of a state s in an NFA?

A All states reachable from s on any input
8
B Only the states reachable from s by exactly one ε-transition
9
C s plus every state reachable from s using only ε-transitions
156
✓ Correct
D All states that have an ε-transition into s
2
175 / 179 answered · 89% correct
Q6 of 10Multiple ChoiceAccuracy60s · 1 pt

Consider this NFA over {a, b}:

──► (0) ──ε──► (1) ──ε──► (2)
     ▲          │          │
     │          b          a
     │          ▼          ▼
     │         (4)       ((3))
     │                     │
     └──────────ε──────────┘

──► marks the start state; ((n)) is accepting.

What is ε-closure(0)?

A {0}
B {0, 1}
3
C {0, 1, 2, 3}
2
D {0, 1, 2}
171
✓ Correct
176 / 179 answered · 97% correct
Q7 of 10Multiple ChoiceAccuracy75s · 1 pt

Consider this NFA over {a, b}:

──► (0) ──ε──► (1) ──ε──► (2)
     ▲          │          │
     │          b          a
     │          ▼          ▼
     │         (4)       ((3))
     │                     │
     └──────────ε──────────┘

──► marks the start state; ((n)) is accepting.

In subset construction, the DFA state {0, 1, 2} reads a. What is the resulting DFA state, ε-closure(move({0, 1, 2}, a))?

A {3}
11
B {0, 1, 2, 3}
148
✓ Correct
C {0, 3}
14
D {2, 3}
5
178 / 179 answered · 83% correct
Q8 of 10Multiple ChoiceAccuracy45s · 1 pt

In the subset construction algorithm, what is the start state of the resulting DFA?

A The ε-closure of the NFA's start state
160
✓ Correct
B The NFA's start state alone
8
C The set of all NFA states
5
D The set of the NFA's accepting states
2
175 / 179 answered · 91% correct
Q9 of 10Multiple ChoiceAccuracy45s · 1 pt

In the subset construction algorithm, which DFA states are accepting?

A Only the DFA state that contains every NFA accepting state
9
B Any DFA state that contains at least one NFA accepting state
167
✓ Correct
C Only the DFA start state
D Any DFA state reached by an ε-transition
1
177 / 179 answered · 94% correct
Q10 of 10Multiple ChoiceAccuracy45s · 1 pt

An NFA has n states. In the worst case, how many states can the DFA built by subset construction have?

A n
18
B n²
7
C 2ⁿ
148
✓ Correct
D 2n
4
177 / 179 answered · 84% correct

Score Distribution

1
2
2
4
5
14
28
56
67
0
1
2
3
4
5
6
7
8
9
10

Score (points) →

Players
179
Average Score
8.7
High Score
10
Max Possible
10
Generated by Buzzer · 2026-10-22 12:24 UTC