February 7, 2011
Classwork 4 (10 pts)
For group work, please turn in one sheet of paper with all the names of those who participated in your group.
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
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).
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: