Reference no: EM133270132

The subset construction technique (for producing deterministic FA from nondeterministic ones) relies heavily on identifying sets of "reachable" states in the nondeterministic machine.

3For the nondeterministic FA for (X* | Y) described below:

1. Which states are reachable from SO using only null transitions?

2. Starting from the set of states identified in part 1, which states are reachable using input character X and null transitions?

The NFA description is as follows:

• it has 8 states: SO,...,S7
• SO is the start state
• S7 is the accept state
• There is a transition from S4 to S5 on X
• There is a transition from S1 to S2 on Y
• There are null transitions from S0 to S1, S0 to S3, S2 to S7, S3 to S6, S5 to S4, S5 to S6, and S6 to S7