**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**

## 0 comments:

## Post a Comment

Let us know your responses and feedback