Pac$-$Man lives on a two$-$dimensional grid that extends infinitely in all directions, and its moves are controlled by a mysterious outside force.

Movement commands come from the alphabet $$\backslash$Sigma $=\backslash$set$\{\backslash$texttt$\{$L$\},\backslash$texttt$\{$R$\},\backslash$texttt$\{$U$\},\backslash$texttt$\{$D$\}\}$$$,$ which correspond to moving $1$ unit left, right, up$,$ and down, respectively.

Pac$-$Man starts from home at the origin $$(0,0)$$$,$ and receives an arbitrary $($finite$)$ string of commands $s $\backslash$in $\backslash$Sigma$^*$$ to execute in sequence.

However, Pac$-$Man first wants to know more about where it will end up after following the sequence of commands in~$s$$.$

$\backslash$begin$\{$parts$\}$

$\backslash$part$[5]$ Define an $\backslash$emph$\{$even position$\}$ in the grid as one in which both the horizontal and vertical coordinates are even numbers.

Give, with brief justification, a DFA that determines whether Pac$-$Man would end up at an even position after completing the sequence of commands in~$s$$.$

If so$,$ the DFA should accept~$s$; otherwise, it should reject~$s$$.$

$\backslash$begin$\{$solution$\}$

$\backslash$end$\{$solution$\}$

$\backslash$part$[8]$ Prove that $\backslash$emph$\{$no$\}$ DFA correctly determines, for an arbitrary command sequence~$s$$,$ whether Pac$-$Man will end up back at home $($at the origin$)$ after completing the commands.

$\backslash$begin$\{$solution$\}$

$\backslash$end$\{$solution$\}$

$\backslash$part$[2]$ In clear and precise English, describe an $\backslash$emph$\{$algorithm$\}$ that, given an arbitrary command sequence~$s$$,$ determines whether Pac$-$Man will end up back at home after completing the sequence.

Briefly justify its correctness, but you do not need to give pseudocode or analyze the running time.

So$,$ while a DFA cannot solve Pac$-$Man's problem, an algorithm $($and hence a Turing machine$)$ can!

$\backslash$begin$\{$solution$\}$

$\backslash$end$\{$solution$\}$

$\backslash$end$\{$parts$\}$