What to submit and when:
Work in pairs
The goals of this lab are:
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 exressions 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
. Also add a note clearly describing (in
English) the language defined by the given regular expression.
When you are done, go to Export and export the resulting NFA, then test it and save it.
Below are the regular expressions:
JFLAP guides you through the process of converting a DFA to a regular experssion 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 a non-empty-set expressions.
Below are the DFAs to convert:Please export and submit your resulting expression.
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 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 fiels 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:
Study the Java regular expressions tutorial. 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.
It is important to know that by default regular expressions will try to find a matching sequence within the given input, not match the entire input.
Your tasks are as follows. Assume case-insensitive matches, unless specified otherwise.
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).
SmithAdams3.jff
(where 3 refers to the question number). This will help me in running test dataInput -> Multiple Runs -> Load Inputs
Convert -> Combine Automata
to copy one automaton into a file for another one.