Open JFLAP and select the Regular
Expression button. Enter the expression a*+ab. We will see how
we can construct an NFA to recognize this language:
a) Select Convert to NFA. You are given a machine that has a single initial and final state with the transition labeled with the regular expression. Clearly this is not a legal NFA since it has a regular expression on a transition. This is a generalized transition graph (GTG). We will need to spit the transition up so that it contains simple input values rather than a regular expression.
b) Select Do Step. This will "De-or" the regular expression by removing the + .
|Explain why the resulting "De-ORed" machine accepts either a* OR
How does de-oring work in general?
c) Select Do Step again. This will "De-concatenate".
|Explain how the de-concatenate works.|
d) Select Do Step a final time to "De-star".
|Explain how the de-starring works|
|Explain the new transition from q0 to q2. Hint: The new transition is the old label OR the label that follows the path from q0 to q1 to q2.|
Click finalize on the table window. If we had more states to remove we would continue this process until we have only the initial and final states left.
Now the regular expression expressed by the FA is displayed at the top of the window.
|Explain why the FA represents that regular expression.
Since we can convert a FA to an RE and we can convert an RE to an FA, it must be the case that these two models of computation represent the same family of languages -- the Regular Languages!