The Gateway to Computer Science Excellence

+2 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.

Thanks!

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.

Thanks!

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.

- All categories
- General Aptitude 1.9k
- Engineering Mathematics 7.5k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.4k
- Theory of Computation 6.2k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.2k
- Non GATE 1.4k
- Others 1.4k
- Admissions 595
- Exam Queries 573
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 18

50,737 questions

57,332 answers

198,441 comments

105,197 users