Cheap and Secure Web Hosting Provider : See Now

# [Answers] Language of walks in a grid – context-free?

, ,
Problem Detail:

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 \$r\$. So would the language be represented as \$L = \{u,d,l,r\}^*\$? If so, this wouldn't be context-free right? Thanks.

#### Answered By : Yuval Filmus

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).

Question Source : http://cs.stackexchange.com/questions/42396

3.2K people like this