Log In
3 votes
Consider the infinite two-dimensional grid G={(m,n)| m and n are  integers}

Every point in G has 4 neighbors, North, South, East, and West, obtained by varying m or n by ± 1. Starting at the origin (0,0), a string of command letters N, S, E, W generates a path in G. For example, the string NWSE generates a path anti-clockwise around a unit square. Further assume that a path is closed if it starts at origin and ends at the origin. (e.g. path NS is also closed).

Let L be the set of all strings over ∑ = {N, S, E, W} that generate a closed path. Which of the following statements is TRUE?

i) L is Regular.

ii) L is context free.

iii) L complement is context free.

in Theory of Computation
edited by
regular ?
No the answer is ii - context free. I want to understand how.

1 Answer

0 votes

Intuitively it looks like $L$ is context-free. It consists of all even length strings (because odd length command strings can never constitute a closed path) where for every N, there is an S (and vice versa) and for every E, there is a W (and vice versa).

$L = \{ NS, SN, EW, WE, NNSS, NSNS, NSSN, ...\}$

You can design a pushdown automaton with two stack symbols $A$ for $N$ and $S$, and $B$ for $E$ and $W$. There will be an initial state, and a set of push and pop states for each direction symbol. Depending on which symbol you see first, you will go to a particular state and push/pop.

Say we have $NNSS$. We see $N$ first, so go to its push state and push $A$. We see $N$ again, so continue to be in its push state and push $A$ again. Now we see $S$, so we transition to $S$'s pop state and pop off an $A$. Do this again on the next. Accept the string by empty store.

This kind of language, which requires us to remember when to push/pop, cannot be modeled as a finite state automaton. L is definitely context-free.

As to whether iii is true, if $L$ is a DCFL, then $L'$ is also a DCFL, which in turn is a CFL. But turns out that $L$ is not a DCFL. Consider the string $NESW$. First we go to $N$'s push state. Next we see $E$. We don't know at this stage whether we are seeing $E$ for the first time or not. So we can go to either $E$'s push state, or its pop state, from $N$'s push state. The machine is non-deterministic, so $L$ is a CFL but not a DCFL.