Here is a GNFA I made from an NFA.

enter image description here

I'm unsure how to treat the node of b(a∪b)* (the first node after the start node and the one below it). Since it doesn't lead to any goal state, do I disregard it in when I generate the regular expression?


Given an NFA, we can simplify it to an equivalent NFA with possibly fewer states by repeatedly applying the following two pruning steps:

  1. Remove any states which are not reachable from the initial state.
  2. Remove any states from which no final state can be reached.

In your case, this will result in removing the left bottom state.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.