[Solved]: Designing a DFA for binary strings having 1 as the fourth character from the end

Problem Detail: 

I came across someone else's old post here

Designing a DFA that accepts strings such that nth character from last satisfies condition

And decided to try it. Apparently it was a homework problem but it was from 2013 so I assume it is okay to discuss it openly by now.

The problem is:

Design a DFA that accepts strings having 1 as the 4th character from the end, on the alphabet {0,1}

The regular expression that does this I believe is (0|1)*1(000|001|010|011|100|101|110|111).

My NFA:

Used Google to see how DFAs work and tried this translation:

Was this a valid solution to the problem?

(Blue arrow = points to starting state, green states are accepting states)

Asked By : Nakano

Answered By : Daniel Martin

You have not created a DFA.

What you have created is a second slightly less messy NFA. (Sort of; as mentioned in comments elsewhere you need the explosion of internal states out from (2) that you have out from (9) in the original NFA)

So let's pretend that we have an NFA that is made by chopping off state (2) in the second picture and adding state (9) from the first picture in its place.

Now, let's walk through the powerset construction on that new NFA:

Start in state {1}. So let's call the DFA state corresponding to the singleton set {1}, DFA_1.

From DFA_1 you can see either a 0 or a 1. On 0, DFA_1 goes to {1}, so DFA_1 again. On 1, it goes to {1,9}. Call that DFA_2.

From DFA_2, on 0 it goes to {1,10,13,16,19}. Call that DFA_3. On 1 it goes to {1,9,22,25,28,31}. Call that DFA_4.

For DFA_3, on 0 it goes to {1,11,14} (since the other nodes only have transitions out on 1). Call that DFA_5. On 1, from DFA_3 we go to {1,9,17,20}. Call that DFA_6.

For DFA_4, on 0 it goes to {1,10,13,16,19,23,26} - call that DFA_7. On 1, DFA_4 goes to {1,9,22,25,28,29,31,32}. Call that DFA_8.

For DFA_5, on 0 it goes to {1,12}. Call that DFA_9. Note that DFA_9 is an accepting state. On 1 it goes to {1,9,15}. Call this DFA_10, also an accepting state.

For DFA_6, on 0 it goes to {1,10,13,16,18,19}. Call this DFA_11. On 1, we get {1,9,21,22,25,28,31}. Call this DFA_12. Note that DFA_11 and DFA_12 are accepting states.

For DFA_7, on 0 it goes to {1,11,14,24}. Call that DFA_13. On 1, we get {1,9,17,20,27}. Call that DFA_14. (DFA states 13 and 14 are accepting states)

For DFA_8, on 0 it goes to {1,10,13,16,19,23,26,30}. Call that DFA_15. On 1, it goes to {1,9,22,25,28,29,31,32,33}. Call that DFA_16. (DFA states 15 and 16 are accepting states)

For DFA_9, on 0 it goes to {1}. We've seen this before! That's DFA_1. On 1 it goes to {1,9}, which is DFA_2.

For DFA_10, on 0 it goes to {1,10,13,16,19}, that is, DFA_3. On 1 it goes to {1,9,22,25,28,31}, that is DFA_4.

For DFA_11, on 0 it goes to {1,11,14}, which is DFA_5. On 1 it goes to {1,9,17,20}, that is, DFA_6.

For DFA_12, on 0 it goes to {1,10,13,16,19,23,26}, or DFA_7. On 1, it goes to {1,9,22,25,28,29,31,32}, or DFA_8.

For DFA_13, on 0 it goes to {1,12} (DFA_9). On 1 it goes to {1,9,15} (DFA_10).

For DFA_14, on 0 it goes to {1,10,13,16,18,19} (DFA_11). On 1, we get {1,9,21,22,25,28,31} (DFA_12)

For DFA_15, on 0 it goes to {1,11,14,24} (DFA_13) On 1, we get {1,9,17,20,27} (DFA_14).

For DFA_16, I hope you can see the pattern by now. On 0 it goes to DFA_15 and on 1 to DFA_16.

So, in summary:

DFA state #  |   Next for 0  |  Next for 1  |  Accepting? ---------------------------------------------------------           1  |       1       |      2       |           2  |       3       |      4       |           3  |       5       |      6       |           4  |       7       |      8       |           5  |       9       |     10       |           6  |      11       |     12       |           7  |      13       |     14       |           8  |      15       |     16       |           9  |       1       |      2       |  yes          10  |       3       |      4       |  yes          11  |       5       |      6       |  yes          12  |       7       |      8       |  yes          13  |       9       |     10       |  yes          14  |      11       |     12       |  yes          15  |      13       |     14       |  yes          16  |      15       |     16       |  yes 

As a side note, I think this process might have been simpler had you started with an NFA of only 5 states corresponding to the regex (0|1)*1((0|1)(0|1)(0|1)).

(Though you'd still end up needing 16 DFA states - it can be proven that that's the minimal number of DFA states needed for this problem)

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/52302

3.2K people like this

 Download Related Notes/Documents