Reply
Sun 12 Feb, 2017 06:11 am
How to make a DFA or NFA for this problem : Consider a game where the start point is randomly chosen and labeled with 3 numbers xyz. There are two players A and B who take turns to play. A player can choose to go from state xyz to x'y'z' only if two digits are the same and the third one is smaller. For example if the state is 342 then if it is A's turn then A can choose to go to 341 or 142 or 312 etc. The winning state/accept state is the state labelled 000. The game halts once a player reaches this state. Show by making an NFA or DFA that if the start
configuration is 111 then the player who plays first always wins. You can assume that A always gets the first turn.