The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
0 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.

asked in Theory of Computation by (83 points)
edited by | 33 views
regular ?
No the answer is ii - context free. I want to understand how.

Please log in or register to answer this question.

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
49,540 questions
54,099 answers
71,006 users