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?
$\begingroup$
$\endgroup$
9
-
1$\begingroup$ I think the best answer is going to be "spend some more time with your textbook to understand the definition of what it means to be regular". The language is regular because it meets the conditions in the definition to qualify as regular. Try drawing the DFA: it will have only finitely many states (1 or 2). See also our reference question: cs.stackexchange.com/q/1331/755 $\endgroup$– D.W. ♦Commented Dec 7, 2015 at 0:56
-
1$\begingroup$ With regard to "limited memory", see Gilles's comment to the answer here. As for your language, what information would you have to know about any string to decide membership? If you know a DFA that recognizes the language, which states does it have and to what pieces of information do they correspond? $\endgroup$– G. BachCommented Dec 7, 2015 at 1:31
-
$\begingroup$ @D.W. I reworded the question. I guess what I'm actually asking, is it true that if $n$ is unbounded that means the expression is not regular? $\endgroup$– CeleritasCommented Dec 7, 2015 at 1:46
-
2$\begingroup$ There are many ways to represent the same language. Some convoluted ways may include $n$ that is unbounded; but this is a contrived representation of the language, rather than an inherent property of it. For instance, the empty language $L=\emptyset$, which you must agree doesn't include any $n$ and is obviously "bounded", can be written as $L=\{ xy \mid x=1^n, y=0^n \text{ for any} n>0 \text { s.t. } |x|<|y|\}$, but although you have an "unbounded" $n$ there - it says nothing about the amount of memory needed. $\endgroup$– Ran G.Commented Dec 7, 2015 at 2:21
-
1$\begingroup$ @Celeritas Can you offer a better yet equivalent definition? The ones we have have the advantage of allowing formal proof. $\endgroup$– RaphaelCommented Dec 7, 2015 at 6:51
|
Show 4 more comments
3 Answers
$\begingroup$
$\endgroup$
3
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.
-
$\begingroup$ Ok thanks for the clarification. I've been in situations where a person is describing the technique to solve a problem but not the problem itself e.g. how to compute the LCM of 2 numbers instead of what the LCM actually is. I thought that's what was happening here. $\endgroup$ Commented Dec 7, 2015 at 3:20
-
$\begingroup$ To answer what you said about prime numbers: the definition of a prime is an integer that's only divisors in one and itself. The technique used to determine if a number is prime would be to test all integers up to the square root of it...or some advanced number theory procedure. $\endgroup$ Commented Dec 7, 2015 at 3:22
-
$\begingroup$ @Celeritas, perhaps you might be partially comforted to hear that there are techniques to help you test whether a language is regular, too. See cs.stackexchange.com/q/1331/755 and cs.stackexchange.com/q/156/755. They are not as automatic as primality testing, so the analogy is not perfect... but hey, it's just an analogy (and certainly imperfect). (Though, fair warning, testing regularity is hard in general.) $\endgroup$– D.W. ♦Commented Dec 7, 2015 at 3:28
$\begingroup$
$\endgroup$
2
The language $\{1^n\mid n>1\}$ is regular because, although you're right that $n$ is unbounded, you don't need to know exactly what $n$ is to accept the language. You only need to be able to tell the difference between "I've seen no $1$s", "I've seen one $1$" and "I've seen more than one $1$". Indeed, these are exactly the states you need in your automaton to accept the language (plus an extra state for "I saw a $0$ somewhere").
answered Dec 7, 2015 at 9:23
-
$\begingroup$ Is it just me or is this answer rendering with corrupted LaTeX? $\endgroup$ Commented Dec 7, 2015 at 9:39
-
1$\begingroup$ @Celeritas Looks fine on my screen (Firefox 37.0.2 on Linux). $\endgroup$ Commented Dec 7, 2015 at 13:45
$\begingroup$
$\endgroup$
1
The set of regular languages over an alphabet is defined recursively as below. Any language belonging to this set is a regular language over .
Definition of Set of Regular Languages :
Basis Clause: , {} and {a} for any symbol a are regular languages. Inductive Clause: If Lr and Ls are regular languages, then Lr Ls , LrLs and Lr* are regular languages.
Extremal Clause: Nothing is a regular language unless it is obtained from the above two clauses.
-
$\begingroup$ This is just the definition of the regular languages. How does it answer the question? $\endgroup$ Commented Dec 7, 2015 at 15:43