CODEWITHSUNDEEP
complexity-theoryautomatadfanfacomputability
pcd13
pcd13

Reputation: 51

NFA Acceptance Confusion

I'm on a senior level theory course, majoring in Computer Science, and was tasked with designing an NFA. If I'm not mistaken, an NFA accepts an input if any path within the NFA can take the string and get to an accepting state. I understand and can create DFAs quite well, and understand the need for NFAs to express problems that would be significantly larger in an equivalent DFA. But I am slightly confused on how specific a NFA has to be to accept something.

For example, one of my homework problems is as follows:

Give an NFA for {w x w^R | x ∈ {0, 1}∗, w ∈ {0, 1}^2},

where, if I interpreted this correctly w^R is the reverse of the string w, x is some binary string of arbitrary length, and w is either "00", "01", "10, "11".

So essentially the NFA would accept a string that starts with w, has some string x, then ends in the reverse of w.

I already designed correctly, albeit very large DFA for this in a previous homework, but the exercise I'm sure is to teach me that NFAs are simpler to use in some contexts than DFAs. I came up with something like this for the answer:

http://s1056.photobucket.com/user/pcd132/media/Untitled_zps4317347c.jpg.html

This NFA accepts pretty much any non-empty binary string, so does it satisfy the question? I'm just confused about the concept of if it somehow, someway accepts something, it should be accepted. Or should I construct it in a way that only accepts the condition somehow, but nothing else? Thanks for the help and clarification if I'm not understanding this.

Upvotes: 2

Views: 540

Answers (1)

Patrick87
Patrick87

Reputation: 28302

You are going to want the NFA to accept all of the strings in your language, and only the strings in your language. One or the other only is not enough (since an NFA for E* is enough to get all the strings, and one that accepts nothing is enough to get only the strings).

There are lots of ways to generate an NFA for this language. One way is to first add 7 states that take all 4 binary strings of length 2. Each one loops to itself on either 0 or 1 to accept any x, and then moves to a unique state in such a way as to start constructing w^R. Each of these states in turns moves to the accepting state in such a way as to complete w^R and accepts.

Upvotes: 0

Related Questions