Language of walks in a grid – context-free? Consider the infinite two-dimensional grid with integer co-ordinates. A walk in the grid can be represented by a string over the alphabet $\{u,d,l,r\}$, where the letters stand for moving one square up, down, left and right, respectively. 

Now consider the langauge of all strings representing closed walks (walks that end at their start point). To me, this would seem like any combination of $u$, $d$, $l$ or&nbsp;$r$. So would the language be represented as $L = \{u,d,l,r\}^*$? If so, this wouldn't be context-free right? Thanks.
If your language $L$ were context-free then so would $L \cap u^* l^* d^* r^*$ be. However, $L \cap u^* l^* d^* r^* = \{ u^n l^m d^n r^m : n,m \geq 0 \}$, which is known not to be context-free (this can be proved using the pumping lemma).