CS 3721
Programming Languages  
Spring 2014
 Recitation 8.   DFAs & NFAs 
Week 9: Mar 18 - 20

Submit following directions at: submissions and rules at: rules. Deadlines are:
  • 2014-03-28  23:59:59 (that's Fri, 28 Mar 2014, 11:59:59 pm) for full credit.
  • 2014-04-01  23:59:59 (that's Tue,  1 Apr 2014, 11:59:59 pm) for 75% credit.

Finite Automata: Read the page FAs. There are many terms, notations, and contrasts here. You must familiarize yourself with those you don't already know, especially the following:

    • symbol (not defined), alphabet, sentence, language, Σ, Σ*, epsilon = ε.
    • FA, state, transition, start state, terminal state
    • NFA, DFA, how an NFA or DFA recognizes sentences from a language.

  1. Consider the finite automaton below. (State 9 is an "accepting" state and States 4 and 5 are "error" or "rejecting" states.)


    FSM for doubles, where "d" stands for any digit (the "suffix" is not included)

    1. Is this an NFA or a DFA? (Always give reasons!)

    2. Suppose the FA processes the string "13.2$" (where '$' is just a terminator that we will often use.) It will start in State 0 and proceed along from state to state as it processes character after character:

      1 3 . 2 $
      0--->1---> 1--->3---> 3--->9

      Explain why this means it has accepted the string?

    3. Do the same for the string "13E+$"? Explain why the result means that it has not accepted the second string.

    4. Write several strings that are recognized by this FA, and give the sequence of states as above. Include enough examples of strings that are accepted so that every arrow of the diagram is used while accepting one of the example strings. (This does not include arrows pointing to "error" states.)

Simulating a DFA: Read the page FA Simulation. You must understand the following items:

    • How a program can simulate the actions of a DFA.
    • How a program can simulate the actions of an NFA. (We won't write any such programs.)

  1. Write a program in C or in Java, perhaps similar to the one at abb (but it doesn't have to be similar), that will simulate (or model) the actions of the following DFA:


    DFA for   /(a|b)*(aa|bb)(a|b)*/

    Use "babaabab$" and "ababaabbabaaa$" as separate inputs to your program. Your program must print the state number after each input character.

    Note: This problem asks for a program. You must always give the source for any program you are asked to write, and you must always give the results of one or more runs of the program (depending on what input data is given). I do not want a zip of some giant Eclipse directory holding everything, but instead I want a single text file with the source files concatenated together, along with output at the end.

Subset Algorithm: Read the page Subset Algorithm. You must understand how this algorithm works and be able to carry it out "by hand" (not using a program).

    You must show your work. You don't need to draw a diagram of the DFA resulting from using the subset algorithm. (You should draw a diagram for your private use in seeing if you seem to have the right answer.) Your answers can look like the items in the link above identified as "Tables" and labeled "DFA". Don't write a table for the input NFA.

  1. Use the subset algorithm to convert the following NFA into a DFA that accepts the same language. (Hint: The DFA also has 4 states.)


    NFA for   /(a|b|c)*(ab|aac)/
    (Intuitively, any string of "a"s, "b"s, and "c"s,
    ending in "ab" or "aac".)

  2. Use the subset algorithm to convert the following NFA into a DFA that accepts the same language.


    NFA for   /(a|b)*(aa)(a|b)*/
    (Intuitively, any string of "a"s, and "b"s,
    containing "aa" somewhere.)

    Note: You must use the subset algorithm, and your answer must be what that algorithm generates. (It turns out that the minimal DFA for this language has one fewer state than the result of the algorithm.)

Revision date: 2014-03-24. (Please use ISO 8601, the International Standard.)