Cheap and Secure Web Hosting Provider : See Now

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

, , No Comments
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.

Asked By : learning_user7

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

Best Answer from StackOverflow

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

3.2K people like this

 Download Related Notes/Documents

0 comments:

Post a Comment

Let us know your responses and feedback