I have an assignment to convert various language descriptions into NFAs and DFAs.
Having graduated with my CompSci B.S. years ago and not touching the topic until my M.S. program, I am racking my brain on one of the questions. I can easily construct a DFA, but the answer must be an NFA that is not also a DFA.
I am not looking for the answer to my homework. I just need guidance on how to construct such a thing.
The question basically states "if a string contains pattern A, it must also contain pattern B" where the order of the two is irrelevant. λ is also acceptable.
My DFA has two branches. Branch 1 looks for pattern A, then does not accept until it encounters pattern B. Branch 2 looks for pattern B, then accepts anything.
I am not sure how to add nondeterministic behavior into this DFA to satisfy the requirements of the assignment. Googling it turns up debates about the complexity/memory tradeoffs of the two approaches, as well as theorems to prove it is possible. But no examples, and that is how I learn best.