In this problem well give a somewhat silly realworld applica

In this problem, we\'ll give a somewhat silly real-world application of NFAs and use them to model a game of tic-tac-toe. Each letter in our alphabet will represent a move a player could make, so there will be 18 letters in our alphabet: X_1...X_9, O_1...O_9, where the letter represents which player is moving and the number represents which space the player is moving to (the top row is numbered 1, 2, 3, middle row 4, 5, 6, bottom row 7, 8, 9). We want to have an NFA that reads in a string written in this alphabet and ends in an accept state if player 1 (the player using X\'s) wins and ends in a reject state if player 2 wins, if the game ends in a draw, or if any player plays in a square that has already been played in or plays out of turn (we say that X goes first). Give a general description of how this NFA would look and how it would operate (you don\'t need to physically draw it, of course). What would the states represent? How many states would there be (roughly)? Which one is the start state?

Solution

1. The states would represent the different permutations of Xs and Os

2. There will be roughly 3^9 states

3. The start state will be the one when the game begins and board is empty.