HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Language of walks in a grid – context-free?

Submitted by: @import:stackexchange-cs··
0
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.

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.