CS 3721 Programming Languages   Fall 2013
Recitation 1. DFAs & NFAs
Week 1: Aug 28 - 30

Submit following directions at: submissions and rules at: rules. Deadlines are: 2013-09-04  23:59:59 (that's Wed, 04 Sep 2013, 11:59:59 pm) for full credit. 2013-09-06  23:59:59 (that's Fri, 06 Sep 2013, 11:59:59 pm) for 75% credit.

Note: Material given below in a blue font is for study.

---

1. Give one reason why a compiled program usually executes much faster than an interpreted program. (Just one reason and not too much for your answer.)

2. Consider the following "C" program:

   #include <whatever.h> int main() { int a[20]; double f, g; int x, y, z; scanf("%lf", &r); while ((a + f)%k != m) { h = f.g(); printf("%s\t%c\t", x, a); if(nonexistent(f,2)) M = 1; // blah, blah } }

   Is this syntactically correct? Is this semantically correct? (Always give reasons for your answers to questions like this.)

---

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

   Note: I intend for you to work out this problem "by hand". It is also permissible to write a program to simulate the given DFA, as in Problem 3 below, but there will be no additional credit for this.

---

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.

---

You must show your work. The answers should look like the items in the link above identified as "Tables".
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.)