Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

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.

share|improve this question

1 Answer 1

up vote 2 down vote accepted

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.

share|improve this answer
    
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. –  John Gaughan Sep 10 '13 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 Sep 10 '13 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. –  John Gaughan Sep 10 '13 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. –  John Gaughan Sep 10 '13 at 3:34

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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