1

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.

Improve this question

1 Answer 1

Reset to default
2

I believe you're having issues because your DFA does not actually solve the problem posed. It accepts AB or B, where the question asks for an automaton that matches AB, BA and ~A (not A).

Since you need both patterns A and B, you can do it like this:

From the initial state q0, our NFA can branch into either of three separate deterministic automata, DFA 1, DFA 2 and DFA 3 with an epsilon-transition.

DFA 1- try matching pattern A, then search for pattern B. If you can match B, accept.

DFA 2- search for pattern B, then search for pattern A. If you can match A, accept.

DFA 3 - search for pattern A, and do not accept if you match A. Accept if you don't match A.

From the initial state, non-deterministically choose between epsilon-transitioning to DFA 1 or DFA 2 or DFA 3.

The main thing about an NFA is that if any of its branches accepts the input, then the input is accepted by the NFA. So, if it matches AB in that order, we accept per branch 1. If it matches BA in that order, we also accept per branch 2. If it doesn't match A, we accept per branch 3.

Improve this answer
4
  • It must accept AB, BA, B, and empty. Also implicitly C can be in there as well: this could be part of pattern A or B that is incomplete, and is essentially ignored in the quest to match A and B.
    – user22815
    Commented Sep 10, 2013 at 3:22
  • You're misunderstanding the question. "If A then B" is satisfied in two cases: 1. both A and B apply, 2. A does not apply. Matching C, B, empty and whatnot are notwithstanding. I'd forgotten "not A" in the original formulation of my answer, but I've corrected that now.
    – Renan Gemignani
    Commented Sep 10, 2013 at 3:26
  • I think I have this, at least at a high level. DFA-2 does not need to match A: once B is matched, that is an accept state. After that A can appear, or random stuff from the language. That was the easy branch anyway. I think I was having a hard time wrapping my brain around how the professor's question was worded: DFA-3 was what I was missing. Asking how to match something natural such as a string representation of a number makes sense and is intuitive: a contrived sequence of zeros and ones is less so.
    – user22815
    Commented Sep 10, 2013 at 3:31
  • There is also a partial match on B, A, then either nothing or a partial match on B. Keep in mind that A and B are just binary sequences. I was simplifying partly so I don't get the answer handed to me, and partly because a more theoretical answer will help more people.
    – user22815
    Commented Sep 10, 2013 at 3:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.