How do NFA's make program design any better when converted DFA form can't remember original states?

Question

Here is some content from the book by Peter-Linz I read

"Consider a game-playing program where the machine needs to make the decision for the next move [say for tic-tac-toe]. Since there are multiple moves possible, we deterministically choose each move and evaluate the move and opt for the best one. Even though the selection process was deterministic and there were many possible moves, the final move made was a single one and was chose as best move while hiding all the tried move-computations from the opponent. [Here we assume that the evaluation process of each possible move was hidden from the opponent].

Hence only one choice was made and opponent is given a illusion such that the move was non-deterministic."

My question is: if an NFA is translated to a DFA for implementation purpose ,how does the DFA make(remember) the correct transitions to the states defined in the original NFA(the game)? My confusion stems from the fact that when an NFA is translated to an DFA it's states get mixed up.

Suppose in a simple game below ,Player is at center position and he wins if he moves leftwards:

if the above DFA is implemented it surely finds a winning state on a "m"(move),but how does it decide whether it was right or left move?

Answer 1

[i]f the above DFA is implemented it surely finds a winning state on a "m"(move),but how does it decide whether it was right or left move?

In the example you gave, it can't. The nondeterministic transition from the start state occurs when a "move" is made. That's all you can possibly know; the machine can't determine whether the winning move was left or right, because those aren't allowed possibilities.

Answer 2

There's something called a Buchi powerset construction which describes what you're looking for.

To give an intuition on how it works, it's kind of like this: Given an NFA, we know if has finitely many states, and at any step of the computation, multiple states can be "active" as a branch at any time. To determine the next step, it's like observing each how each branch reacts to the next symbol in the input.

So, construct each state in the DFA as a subset of the states in the NFA. Then, add a transition from a subset to another subset based on how each of the active states in that subset react to the next symbol in the

To demonstrate the transitions between sets let's say I design an NFA as follows:

It has 3 states {$q_1, q_2, q_3$} and the transition function works like this,

$\delta(q_1,a)=\{q_2,q_3\}$

$\delta(q_2,b)=\{q_1\}$

$\delta(q_3,b)=\{q_2\}$

It's an artificial example without accepting states, it's just to show how the transition works.

So as an NFA, if it starts on $q_1$ and we gave it "ab" as an input, then the sequence of set of states that the NFA goes through is: $\{q_1\}, \{q_2,q_3\}, \{q_1,q_2\}$ .

it's the same as just making these sets into a state for a DFA like so:

DFA has states: $\{q_a, a_b, q_c\}$, letting $q_a$ represent $\{q_1\}$, $q_b$ represent $\{q_2,q_3\}$ and $q_c$ represent $\{q_1,q_2\}$

$\delta(q_a,a)=q_b$

$\delta(q_b,b)=q_c$

It's quite tedious to go through the entire $2^n$ states so usually after something like that sort of construction you can try to minimise it using a DFA minimisation algorithm or just by considering which states are useless and what transitions can be shortened after.

Answer 3

You asked:

my question is if NFA is translated to DFA for implementation purpose

I think that the premise of the question is not correct, since it is clearly stated by the author (at least according to your question) that:

Since there are multiple moves possible, we deterministically choose each move and evaluate the move and opt for the best one.

So from the outset it is clear that any Non-determinism is just a result of abstracting the Deterministic Finite machine. So in this particular case, the conversion (loosely stated) is from a DFA to an NFA and not otherwise.

Coming to your question specifically, the DFA and NFA have different states altogether. The states from an NFA (say $S_n$) are used to construct the new states for the DFA (say $S_d$) and once they have been constructed, the DFA only tends to $S_d$. There is no need for the DFA to remember $S_n$ and the associated transitions.

Thus to sum it up, the DFA does not make transitions to the states $S_n$. It only makes transitions between the various states $S_d$.

Answer 4

In this particular example, the problem is that the transition labels are just "move". This violates the idea that the NFA represents a language that we are interested in if we later want to find out which move was the right one. Hence the NFA to DFA translation makes little sense in this case.

A simple solution would be to label every transition in the NFA by the last move taken by one of the two players, and then determinizing the NFA would retain this information.

(This is, if I get your question right. If you study games, you normally model your game as as game, rather than an NFA).