I have these grammar rules defined as follows,

FDEF -> #feature #: FEXP
FEXP -> #op #( FLIST #)
FLIST -> FEXP #, FEXP | #feature

I know how to derive the derivative tree for a given string from this, but how do I draw a NFA for this string {#feature #: #op #( #feature #)}*. I have seen many examples which they draw the NFA from a regular expression, if so can I consider this string as a regular expression? If not how can I draw it?


I will leave the actual drawing up to you, but I will describe it here. You can draw a directed graph, with a start state that follows the input #feature to another node which follows an edge to #: to #op to #( to #feature to #). The node that we land on after #) is the accept state. If it any point, we read some input that does not allow us to follow that path, we immediately travel to another state (in this case, a designated reject state) with no output paths.

Our accept state will only have one out edge, which we follow on the input #feature. This takes us back to where we traveled after our start state. If we read any other input from our accept state, we move to the designated reject state.

| cite | improve this answer | |
  • $\begingroup$ Is this what you explained? i.imgur.com/dbDPCrC.jpg Should I mention the reject state too? if so what should I mention on my edges that goes to reject state? $\endgroup$ – Marlon Abeykoon Jul 18 '18 at 5:29
  • $\begingroup$ Yes that is what I mean. You would still want a "sink" state, that is a reject state that only self-loops on all inputs. All your other states would transition to this reject state on all other input that you don't have defined above. In this case, your NFA will also be a DFA $\endgroup$ – koverman47 Jul 18 '18 at 14:30

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.