CSci 3501 Algorithms and Computability - Lab 10.
November 2. Due Monday, November 9th 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
Task 1: 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 is the DFA to convert:
- The language of all strings with 00 pattern
- 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.
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:
- 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.
- 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.