Because NFSMs do not correspond directly to any realizable hardware implementation, their generation from regular expressions does not completely solve the problem of systematic construction of regular-expression recognizers. To bridge the gap between an NFSM and a real implementation, we explore the problem of deriving an equivalent (deterministic) FSM from a specified NFSM.
A. Draw the state-transition diagram for a deterministic FSM that is equivalent to the NFSM you constructed in problem 6.21, which recognizes the strings A( (ABC)( (ACB))*A.
B. Is the amount of state information associated with an NFSM at any moment always finite? If so, can you place a bound on the state information required for operation of an n-state NFSM? Mat does your answer imply about the number of states required by an equivalent deterministic FSM? (Hint: Consider the token-based model of NFSM operation in section 6.5.)
C. Describe a general procedure for the systematic derivation of a deterministic FSM from a given nondeterministic one. Explain the relationship between states of the deterministic FSM and states of the NFSM from which it is derived.
