World's most popular travel blog for travel bloggers.

[Solved]: Why is $\{1^n \mid n > 1\}$ regular?

, , No Comments
Problem Detail: 

Given the definition of a regular language is one that can be expressed with finite memory, how is $\{1^n \mid n \geq 1\}$ regular? The $n$ is unbounded. I know a DFA can be drawn, which means the language is regular. But I thought another condition is that $n$ must be bounded, so it's as if the 2 tests contradict each other?

Asked By : Celeritas

Answered By : D.W.

If I understand you correctly, the following comment seems to get to the heart of what you're really asking:

A regular language is one where you can make an automata for it, or a regular expression for it. But this seems like a poor definition to me because how do you know if none exist or you just haven't been able to think it up yet?

That's a fair question. I'm afraid the answer is -- the definition is what it is. Whether you consider it poor or not, this is the standard definition of a regular language. For now, I recommend that you simply accept it and work within it. I agree that the implications are a bit.. uncomfortable. Unfortunately, that's life.

Many definitions are like this. For instance, consider the definition of what it means for a number to be prime: a number $n$ is prime if there it does not have any divisor $d$ such that $1<d<n$. Of course you can ask: how do you know if such a divisor exists? Maybe you just haven't been able to find one yet? The answer is that you might not know... but that's still the definition, and there are good reasons to use this definition, rather than some other.

Ultimately, there are reasons why the standard definition of regular languages is useful. Those reasons might not be obvious when you are first starting to study the material. From a computer scientist's perspective, one reason why the notion of a regular language is useful is that it corresponds to what can be accepted by an automaton with finite state, and this has many applications through computer science (parsing by compilers, model checking, and more). From a mathematician's perspective, the notion of a regular language is interesting because it has many useful properties.

But for now... accept that the definition is what it is, and there are reasons for it to be that way, and go with it.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/50425

3.2K people like this

 Download Related Notes/Documents

0 comments:

Post a Comment

Let us know your responses and feedback