What to submit and when:

- All submissions are electronic: by e-mail to elenam at morris.umn.edu and CC to all lab partners. Please do not delete your e-mail from "Sent mail" or your mailbox until the end of the semester.
- When working on the lab, please comment your work so that it is clear what contributions of each person are.
- At the end of the lab each group should send me the results of their in-class work. Please indicate if this is your final submission.
- If your submission at the end of the lab time was not final, please send me(CC to the lab partner(s)) a final copy before the due time. Please use the subject "3501 Lab N", where N is the lab number.

Work in pairs

The goal of the lab is to explore combining finite automata, conversion between DFAs, NFAs and regular expressions, and to get practice with regular expression.

- Please save your automata files as .jff files and your data as
.txt files.
**Files names must be as follows**: names of those in the group followed by question name, e.g.`SmithAdams3.jff`

(where 3 refers to the question number). This will help me in running test data - To load test data from a file, go to
`Input -> Multiple Runs -> Load Inputs`

- When adding multiple transitions between the same two states, add them one by one. Typing "0, 1" in a label for an arrow will give you a wrong result since the automaton will try to match this input exactly, including the comma.
- When writing DFA, check that every state has a transition on every symbol. JFLAP does not check it.
- Use
`Convert -> Combine Automata`

to copy one automaton into a file for another one. - Consult the JFLAP tutorial as needed.

Unless specified otherwise, the alphabet is the set of 0 and 1.

- Construct an automaton (DFA or NFA) for a concatenation of the following languages: a language of all strings of an odd length and a language of strings that can be represented as a non-empty sequence of 1s followed by a non-empty sequence of 0s. Test the automaton carefully.
- Construct an automaton (DFA or NFA) for A* (* stands for the "star" regular operation), where A is the language of strings of length at least two with no occurrences of the pattern 00. Think carefully of what the language is. Use the * construction for NFA. Test the automaton thoroughly.
- 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.
- 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.

Use the tutorial Regular Expressions and Converting to an NFA to convert the regular expressions given below to NFAs. Note that JFLAP uses + as a symbol for union and * for the star operation. Also make sure to set parentheses correctly in your expression.

JFLAP gives you hints on the steps and provides a button "(D)e-expressionify Transition" to break down regular expressions into smaller subexpressions. You need to add the empty transitions to complete each step.

As you are converting a regular expression to an NFA, write down the
intermediate expressions as a note on the JFLAP screen: use the
selection tool (the one that you use to mark initial and final
states), right-click anywhere on the JFLAP screen, and choose "add
note". For instance, if you are breaking down an expression
`00+11`

into `00`

and `11`

, write
`00+11 -> 00, 11`

.

Below are two regular expressions to convert:

- ((0+1)0)*
- (00)*+(10)*

Please export and submit your resulting expression.

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.

- Find all occurrences of letter combinations "dfa" and "nfa" in a text.
- 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 ).
- Find all negative integer numbers, i.e. numbers preceded by a - sign
- Find all words that start with a letter t (hint: use boundary matches http://java.sun.com/docs/books/tutorial/essential/regex/bounds.html
- Find all words in a text that have letters t and/or i in the them (in any order)
- Use the doRegExSplit to split a string into items separated by |
- 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).

- Submit your JFLAP files as attachments, CC your group. Make sure to submit your automata files (as .jff) and your input data (as .txt). Make sure to follow the naming requirements! Make it clear which data refers to which automaton.
- For the Java part submit all of your .java files (separately or zipped)

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.