CSci 3501 Algorithms and Computability - Lab 9.

November 13. Due Friday, November 21 at 11:59pm

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.

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

• 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.
• Do not use "convert to DFA" or "minimize DFA" options.
• Consult the JFLAP tutorial as needed.

Lab tasks

Lab task 1: convert regular expressions to an NFA (6 points)

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 "(De)-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:

1. ((0+1)0)*
2. (00)*+(10)*

Please export and submit your NFAs.

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 ).
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).

Task 3: Convert a DFA to a regular expression (4 points)

JFLAP guides you through the process of converting a DFA to a regular expression via a generalized NFA (GNFA), as described in the tutorial Converting a FA to a Regular Expression. JFLAP uses a slightly different version of a GNFA: it allows self-loops in the starting and the final state. The empty set transitions are added just like in the book, and the number of states is reduced by the procedure described in the book. The resulting regular expression then is combined as R1*R2R3*, where R1 is the self-loop expression in the start state, R2 is the expression on the transition from the start state to the final state, and R3 is the loop in the final state.

As you are transforming your DFA to a 2-state GNFA, write down (in a plain-text file) all transition changes that result in non-empty-set expressions.

1. The language of all strings with 00 pattern

Please export and submit your resulting expression.

Task 4: Play the "pumping lemma game" (6 points)

The pumping lemma in JFLAP is implemented as a two-player "game" when one player is trying to prove that a language is regular by representing strings as required by the pumping lemma, and the other player is trying to disprove it, as described in the tutorial Regular Pumping Lemmas.

Go to "Regular Pumping Lemma" in the JFLAP start menu (careful: you don't want Context-Free Pumping Lemma). There is a list of languages, some are regular, some aren't. The alphabet is a,b. The pumping length is denoted as m. JFLAP allows you to save the file with the log of all your attempts. Please submit these files for the two cases below and additionally write down your conclusions in a plain-text file or an e-mail message.

Your conclusions should include:

• whether the language satisfies the pumping lemma. This is a bit tricky since you are testing a pumping length, but your conclusions should be general. For a language that satisfies the pumping lemma show its pumping length and explain how you would always be able to break down a string that in a way that satisfies the pumping lemma. If the language does not satisfy the pumping lemma, show how to construct a string that breaks the pumping lemma. Show it for at least two values of candidates for the pumping length.
• whether it is regular (note that some languages that satisfy the pumping lemma may still be non-regular). Justify your answer, either by explaining why the language is regular, or by giving your intuition for why it is not regular. You don't need to do a proof.

The languages to try:

1. The 6th example (the language a^n b^j a^k, where n > 5, j > 3, and k ≤ j). Choose the "computer goes first" option so that you are trying to prove that the language is non-regular.
2. The 8th example (the language a^n b^k, n is odd or k is even). Choose the "you go first" option so that you are trying to prove that the language satisfies the pumping lemma.

What to submit

• Submit your JFLAP files as attachments, CC your group. Make sure to submit your DFA 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.

CSci 3501 course web site.