CS402 Theory of Automata GDB Solution Spring 2014

If we would require to implement chess game, what would be the suggested automata / machine from the list given below. Also provide reason(s) in 2 – 3 lines to support your choice.

1 – FA

2 – NFA

3 – TG

4 – TM

5 – Derivation Tree

Solution: For Chess game we use FA. because Chess game have to end. Chess game ended because of checkmate, stalemate, draw or resignation, Draws are very important here. The can happen when the position is repeated three time, there is a perpetual check, or by the 50 move rule.
so, it means that there is a finite number of moves in any chess game. Hence we can use Finite Automaton to build a chess game.