CSci 3501 Algorithms and Computability - Lab 10.

November 9. Due Wednesday, November 15 at 11:59pm

What to submit and when:

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 explore the pumping lemma for regular languages.

Using JFLAP and naming your files

Lab tasks

Lab task 1: convert regular expressions to an NFA (8 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.

Lab Task 2: 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:

  1. The language of all strings that have 00
  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.

Please export and submit your resulting expression.

Lab task 3: Play the "pumping lemma game" (8 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:

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.

Lab Task 4: Context-free grammars and pushdown automata (20 points)

Please refer to the corresponding sections of the JFLAP tutorial, namely Entering grammars (just pressing "enter" on the right hand side enters an empty string), Brute Force Parser for constructing parse trees, and Constructing a push-down automaton. If Brute Force Parser doesn't work on your grammar, contsruct your parse tree manually using User Control Parser.

Your tasks are as follows:

  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
  3. A context-free grammar for odd-length strings of alternating zeros and ones. It can start with either zero or one.
  4. A context-free grammar for a language of 0, 1, true, false, operations <, >, == , a ternary conditional operator ?:, and parentheses. The order of precedence is as follows: parentheses have the highest precedence, then the comparison operations, and then the conditional operator.

    The conditional operator is defined as following:

    e1? e2 : e3
    evalautes e1, and if it is true then it evaluates and returns e2, otherwise it evaluates and returns e3. For example:
     0 < 1? 0 : 1
    would be interpreted as
    
    (0 < 1) ? 0 : 1
    
    which becomes
    
    true ? 0 : 1 
    
    after the condition is evaluated, which would in turn result in 0.

    The comparison operators <, >, == are left-associative, i.e.

    0 == 1 == false
    should be interpreted as
    (0 == 1) == false
    which evaluates to
    false == false
    which is true.

    The conditional is right-associative:

     0 > 1 ? 0 : 0 == 0 ? 1 : 0
    is interpreted as
    (0 > 1) ? 0 : ((0 == 0) ? 1 : 0) 
    then evaluated as
    false ? 0 : ((0 == 0) ? 1 : 0)
    then as
    false ? 0 : (true ? 1 : 0)
    then as
    false ? 0 : 1
    which will return 1.

    Test your grammar on all of the test cases above and two more cases that check for precedence, associativity, and parentheses. Submit jpg files for the parse trees.

    Note that language designers don't always get the associativity right.

    Important: your grammar must enforce correct precedence and associativity for all operations. Your write-up for this problem should briefly explain how this is done.

  5. A pushdown automaton for the language of strings a^k followed by any number of b followed by c^k (do not convert your grammar from the previous question into an automaton or vice versa)
  6. A pushdown automaton for the language of strings a^n b^m where n <= m.

Lab Task 5: Convert context-free grammars to pushdown automata (3 points)

Use the option Convert CFG to PDA (LL) for this problem. In a plain-text file explain what rules were added to the PDA and why.

  1. Convert the grammar for the language of palindromes to a PDA. The alphabet is 0,1. Submit the resulting PDA.

CSci 3501 course web site.

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.