CIS-6050 Homework #3 (Regular Expressions)

Due: Friday, March 22, 2019

Review Chapter 2 in the text. Most of the methods and algorithms needed for this assignment are described in that chapter.

The goal of this assignment is to complete NFA.scala as currently defined in the Dragon module of the Augusta project. In particular, implement the methods union, kleeneClosure, and toDFA. When you are done the program NFAExample.scala should run as expected.

Note that in this formulation, a DFA is considered a special case of an NFA. You should reflect on if this is really a good design choice. If it seems better (or necessary) you could create a separate DFA class, but this isn't specifically required for this assignment.

Ultimately one would want a standalone program that takes as input a regular expression (RE) and a string, and outputs "match" or "no match" depending on if the RE matches the string. For example:

  > a*ba aaaaaba
  > a*ba aaaaab
  no match
  > a*ba ba

This is actually a bit of a hassle because REs have their own syntax that needs to be parsed. Thus for this assignment you can hard code a representation of the RE being tested into your program as is done in NFAExample.scala.

The DFA created by the subset construction algorithm is not very optimal. Implement a state minimization algorithm such as Hopcroft's Algorithm (as described in the text). Executing the state minimization takes time. Under what conditions do you think it would be worth doing?

Submit your modified NFAExample.scala to Moodle.

Last Revised: 2019-03-03
© Copyright 2019 by Peter C. Chapin <>