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

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?

• I don't see the connection between the quote and DFAs/NFAs. What is the context of the quote? – Yuval Filmus Feb 16 '18 at 7:29
• game design uses NFAs for choosing the best move – Arthik Vishwakarma Feb 16 '18 at 7:37
• If "game design uses NFAs for choosing the best move", then this may simply be a decision done by the author of the article/book, perhaps to base the presented techniques on something that the reader already knows. The downside of such an approach is that this makes the presentation inprecise, hence your question. There is the field of study of games in CS (see, e.g., en.wikipedia.org/wiki/Parity_game) where the definition of a game captures the interaction between the players quite nicely. What you would normally use for TicTacToe would be like a tree-shaped reachability game. – DCTLib Feb 16 '18 at 9:03
• I don't understand your question. The quoted text says nothing about automata, so why do you assume it's talking about automata? – David Richerby Aug 15 '18 at 18:30

[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.

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.

• dear @CurryKatsuCutlet I know subset construction,please see the question i have posted again. – Arthik Vishwakarma Feb 16 '18 at 5:24
• Could you elaborate on what you mean then by "how does the DFA make the correct transitions to the states defined in the original NFA"? Edit: If you're asking about how a DFA can remember the states an NFA has made, I'm sure there are ways to do it with some modification, by adding extra states to keep track of what the NFA has previously visited for example. But since a DFA is finite in memory, you can only remember up to a finite amount of previous steps the NFA has made. – CurryKatsuCutlet Feb 16 '18 at 5:49
• i have edited the question .please see it again. – Arthik Vishwakarma Feb 16 '18 at 6:17

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$.

• in the above question i have posted,how can DFA decide whether it was right move or left move that caused its win,it has to determine because the player has to move his piece .we can determine through nfa but it cannot be implemented in a computer.How can we achieve this?the right choice of moving in a computer? – Arthik Vishwakarma Feb 16 '18 at 6:44
• We can achieve it by writing proper algorithms. Read up on Minimax algorithms to understand how an optimal move can be found for a game like Tic-Tac-Toe. This algorithm just simulates a particular DFA. – Sagnik Feb 16 '18 at 6:50
• This doesn't answer the question asked. – reinierpost Feb 16 '18 at 11:26

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).

• why can't we find out ,in the example i have cited in the post ,there is a unique transition of states that leads to a winning state.could you elaborate on that? – Arthik Vishwakarma Feb 16 '18 at 12:39
• A language is a subset of words of an alphabet $\Sigma$. If you alphabet is $\Sigma = \{M\}$, as it seems like to be the case in your NFA, then what the automaton represents is a subset of $\Sigma^* = \{\epsilon, M, MM, \ldots\}$. If you want to find out which move led to winning the game and this is not represented in the language of the automaton, then you use an automaton for something other than it was defined for, namely representing a language. There are no states in a language - only words that are accepted. – DCTLib Feb 16 '18 at 14:04