CompSci 18S - Spring 2007 - Finite Automata

For group work, please turn in one sheet of paper with all the names of those who participated in your group.

Problem

Finite automata (FA) are used in many disciplines to model a problem. An FA is a graph that has states(or nodes) and transitions (or edges). The transitions show how to move from one state to another. One state is indicated as the initial (or start) state (an arrow into it), and one or more states can be final states (indicated by two circles). A transition is labeled with a character. A transition between two states means that the transition is processed (character is recognized) if you move from one state to another.

For example, consider the finite automaton shown below that recognizes strings that have an even number of a's and an even number of b's.

The initial state is q0. There is only one final state, which also happens to be q0. What is the language of this FA? All strings that start in the start state and end in the final state are accepted by this FA and in its language. Try tracing the string aababbba, starting in q0 and ending in q0. Try tracing the string aba, which is not in the language. It does not end up in q0.

Each state has meaning, representing the part of the string that has been processed to reach it. Here is the FA again, annotated with the meaning of each state. If you are in state q1, then you have seen an odd number of a's so far, and an even number of b's.

We will use the tool JFLAP (you used it earlier for L-Systems) to create some FA. If you don't have it, you can get it from: www.jflap.org

Problems

1. Create the FA above in JFLAP. Start JFLAP and select Finite Automaton from the menu page. In the editor, there are four buttons. The second button is for creating states. Click on it, and then click anywhere on the canvas to create a state. The second button (the arrow pointing up and to the right) is for creating transitions. Click on a state (and hold the mouse button down), then release on a second state. You will be prompted for the transition's label, and then the labeled transition will be created. The first button is for "fixing things up". After selecting it you can click on a state and move it to a different position, or you can right click on a state and select initial or final state. You can also add a label to annotate your FA.

   After creating your FA, test it on input strings. First select "Input", "Step with Closure" and trace through the string aababbba. Then select "Input", "Multiple Run" and trace through several other strings, some in the language of the FA and some that are not (they should be rejected).

2. Using JFLAP write FA for the following languages.

   First list 5 strings that should be accepted, and five strings that should not be accepted and get them checked off.

   Then build the FA and test it in JFLAP.

   Then draw the final FA to turn in.

   Here are the Languages:

   1. The alphabet is {0,1}. Accept binary numbers with an even number of one's.

   2. The alphabet is {a,b}. Accept strings that have exactly two or three b's, and the number of a's is divisible by 3.

3. On paper (not in JFLAP), write an FA to recognize valid Java variable names. You can use short cuts like (A-Z) to mean "any of A-Z".

4. On paper (not in JFLAP), write an FA to recognize valid integers in Java. Note they could be negative.