patternMinor
Language of walks in a grid – context-free?
Viewed 0 times
gridfreelanguagecontextwalks
Problem
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.
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.
Solution
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).
Context
StackExchange Computer Science Q#42396, answer score: 7
Revisions (0)
No revisions yet.