SOME NOTES ON LAMBDA TRANSITIONS
N. Guydosh - 9/15/00
Concept: Lambda Closure: -closure of some state q0 is the set of all states (vertices) p such that there is a path (see definition of path) from p0 to p labeled . Note that the path may go though more than one state (from Hopcroft and Ullman, p. 25).
OR: -closure(q0) = {q0} {all points reachable from q0 by paths labeled by }
Notes on transitions (these are demonstratable on the FSM Simulator):
- cannot be explicitly expressed in an input string for the simulator since it is not part of the alphabet .
-All transitions from a target state are always taken on any transition to this state
( closure). From FSM simulator user document (fsmdoc.txt):
SPECIAL NOTE ON NFA SIMULATIONS
... The initial state appears as the epsilonclosure (lambdaclosure) of the initial state, Figure 13. Each transition moves to a new set of states, taking the epsilonclosure (lambdaclosure) each time, Figure 14. The input, is accepted if the set contains a final state, ...
-The initial “current” subset of states is the closure of the initial state q0, and obviously contains q0 itself.
-In general, when we make a transition to some state q, the closure of q is taken as the transition is made into q. Thus the closure of q in addition to q will automatically be added to the next state subset as q is entered.
-From another point of view (see fig. 1 below): Suppose a state q1 has an outgoing edge labeled b, and also an outgoing edge labeled (explicitly defined transition). In order to “invoke” the “b” transition, q1 must be included in the “current state subset”, and “b” must be the next input. But the transition is always realized on enteringthe q1 state, ie., when q1 is entered from the previous transition, the closure is accomplished and the state on the other end of the edge gets instantly activated.
But note that on the “next cycle” (after entering q1) with an input of b, the link from q1 going to some other state q2 (which in turn has an outgoing edge labeled ‘b’), can be invoked again (on the next cycle after entering q1) as “b” = “b”. Also the b link from q1 to some other state q4 (which in turn has an outgoing edge labeled ), can be invoked again on the next cycle as “b” = “b“- thus also activating q5 via .
-Each state in an NFA has an implied transition to itself. But this transition cannot be explicitly shown in the input string (as ). It will be taken in a closure, ie., if the transition is to state q, then q is always included in the subset of next states (sort of trivial result).
-The only way we can explicitly show a transition on the simulator is in the initial state. In this case, the transition is represented by no string (no symbols) and not itself. If q0 F (final states), the this string is accepted, else it is rejected.
-If the initial state q0 has a transition to some other state, say q, then before any cycles are taken, q will appear the current state subset along with q0.
-NOTE: *(q,a) is not necessarily equal to (q,a), since *(q,a) includes all states reachable from q by paths labeled a including paths with arcs labeled, while (q,a) includes only those states reachable from q by arcs labeled a. (Hopcroft and Ullman, p. 25).
In fig 1. Below:
(q1,b) = { q4, q6} ... Only explicit “b” transitions, can be used to specify NFA
*(q1,b) = {q4, q6, q3, q5} ... includes transitions
transition to q3 results from b or the b transition from q2 after closure on entering q1. Transition to q4 is due to b, and to q5 is due to b.
Transitions in an NFA with transitions are done with the * function applied to singleton strings as arguments and implied transitions.
Figure 1. “\”means , = {b}, and q0 is the initial state., All non lambda transitions are b transitions