CSci 3501 Algorithms and Computability - Lab 9.

October 23. Due Monday, October 30 at 11:59pm

What to submit and when:

Lab assignment

Work in pairs

Lab overview and goals

The goal of the lab is to practice with JFLAP (a tool for experimenting with finite automata and other computability topics) and to design and test finite automata (DFAs and NFAs).

Using JFLAP and naming your files

Lab tasks

Task 1: convert an NFA to DFA (8 points)

  1. Use the "convert to DFA" function of JFLAP to convert an NFA for the language of all strings with at least two 0s to a DFA.
  2. Use the "convert to DFA" function of JFLAP to convert an NFA for the language of all strings that end with two 1s to a DFA.

Task 2: Java regular expressions (20 points)

Study the Java regular expressions tutorial (ignore the Test Harness section, we use our own testing class). Note that instead of using the Pattern and Matcher classes directly, you will be using the class RegExTester that provides methods for searching, splitting, and replacing strings based on regular expressions. Study examples in main in that class.

Important: by default regular expressions will find a matching sequence within the given input; they do not match the entire input. For instance, a regular expression "DFA" will find a match in an input "DFAs are cool".

Also important: Java strings use \ as a special character. Therefore you need \\ for predefined regex classes, e.g. "\\d+" matches one or more digit. See a link to more predefined classes in question 2 below.

Your tasks are as follows. Assume case-insensitive matches, unless specified otherwise.

  1. Find all occurrences of letter combinations "dfa" and "nfa" in a text.
  2. Find all integer numbers (i.e. sequences of digits with no other characters) in a text. Use a predefined class \d to match a single digit (see example here: http://java.sun.com/docs/books/tutorial/essential/regex/pre_char_classes.html ). Ignore the negative sign.
  3. Find all negative integer numbers, i.e. numbers preceded by a - sign
  4. Find all words that start with a letter t (hint: use boundary matches http://java.sun.com/docs/books/tutorial/essential/regex/bounds.html)
  5. Find all words in a text that have letters t and/or i in the them (in any order)
  6. Use the doRegExSplit to split a string into items separated by |
  7. Use the doRegExReplace method to replace all occurrences of "today" by "yesterday".

Make sure to submit your code (with some method calls commented out) and a copy of your test data for each regular expression (as a separate file or in comments).


What to submit

CSci 3501 course web site.

The views and opinions expressed in this page are strictly those of the page author. The contents of this page have not been reviewed or approved by the University of Minnesota.