## CSci 3501 Algorithms and Computability - Lab 10.

#### Due Wednesday, November 3rd at 11:59pm

What to submit and when:

• All submissions are electronic: by e-mail to 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 get practice with regular expressions, the pumping lemma, and simple context-free grammars.

#### Convert a DFA to a regular expression (8 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.

Below are the DFAs to convert:

1. The language of all strings with 00 pattern
2. The language of all strings that either start with 0 and don't have any more 0s, or start with 1 and don't have any more 1s. Note that as the first step you would need to create a single final state and connect the old final states to it by empty-string transitions.

#### 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 (show an example that breaks it or briefly describe a strategy that makes it work) and whether it is regular (note that some languages that satisfy the pumping lemma may still be non-regular).

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.

#### CFG (6 points)

Use the corresponding sections of JFLAP tutorial as a reference. Define the following in JFLAP:

1. A context free grammar for the language of strings a^n b^m, where n >= m
2. A context free grammar for the language of strings a^k followed by any number of b followed by c^k

#### What to submit

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

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.