CSCI 439 Quiz 2 (2025) Prep Notes

Preparation for CSCI 439 Quiz 2 (2025)

As per the exams page, the quiz will be closed book, closed notes, no electronics, and held in the lab during your scheduled lab section. You will have 50 minutes to complete the quiz.

You are permitted one double-sided 8.5x11" page of notes ('cheat sheet').

This second quiz is again primarily theory, focused on the lecture material through Feb. 12th, emphasizing the process of transforming regular expressions into minimized DFAs. The quiz will not cover yacc/lex.

There will be three questions with an emphasis on the following:

Topic: applying Thompson's construction techniques to develop an NFA from a regular expression
- e.g. Given the following regular expression, apply Thompson's construction techniques to develop an NFA that recognizes the same set of strings.
Topic: applying the subset construction technique to develop a (not necessarily minimal) DFA from an NFA
- e.g. Given the NFA described by the following table, apply the subset construction technique to develop a DFA that recognizes the same set of strings.
Topic: applying Hopcroft's technique to produce a minimal DFA from a non-minimal DFA
- e.g. Given the DFA described by the following table, apply Hopcroft's technique to develop a minimal DFA that recognizes the same set of strings.

Suggested practice:

Below are two starting regular expressions, one simpler and one a bit more involved. Apply the three techniques (Thompson's, subset, Hopcroft's) in sequence to develop minimal DFAs for each of the two regexes.

( 0 | (0|1)*00 ) (represents evenly binary integers divisible by 4)
( 0 | (1(01*0)1) )+ (represents binary integers evenly divisible by 3)
(Trivia: the 1(01*0)1 effectively represents 2^N + 2^N-1 - 3, which you can convince yourself does actually provide multiples of 3, and the overall regex is combining multiples of this so still produces multiples of 3.)

When checking your answers for these two, the final result (after Hopcroft) should boil down to DFAs with four states:

In part 1 you effectively wind up with a start state (nothing read), an accept state, a state where you've just read a 1, and a state where you've just read a single 0 after a 1.
In part 2 you effectively wind up with a start state (nothing read), an accept state (the string read so far represents an integer divisible by 3), a state where the value read so far represents an integer with a remainder of 1 after dividing by 3, and a state where the value read so far represents an integer with a remainder of 2 after dividing by 3.

Note: in the quiz questions I'll give you specific regular expressions, NFAs, and DFAs to start from in the respective questions (to avoid potential problems in one answer from cascading into later questions).