5
Wack
7y

Question: when modeling a language using a nondeterministic finite state machine, do I have to add a "trash" state, if a deterministic one would need one or can it just be obmited and if so why?

Comments
  • 0
    "Trash state" refering to a sink from which no condition that would be acceptable is reachable.
  • 0
    nondeterminism means that a trash state is not necessary
  • 0
    It's not necessary because by the def'n of an NFA you don't have to have paths for every letter in your alphabet and if there is no path corresponding to an input that state is removed (essentially what you're doing with a trash state).
  • 0
    Alright. Supose I got a language like L = {0,1}* and want to match if the amont of 0 mod 3 is equal to 1, do I then just need to states, let's call them p0 and p1, where init points to p0 and then arrows for the input of 0 from p0->p0, p0->p1, p1->p0 and p1->p1, with p1 as accepting state?
  • 0
    So I'm still kind of stuck. Any fellow CS student care to help me out? I need to make a NFA but got stuck there, so I created first 3 FA (no problem), tried to merge them, which kind of is a cluster fuck when trying to merge FA1 and FA2... But how the fuck do I create a NFA out of it?
Add Comment