A computer's memory is finite, so how can there be languages more powerful than regular?

A computer has a finite memory. There are no computers with infinite memory. Therefore the only languages that a computer can process are those whose member strings are finite. As I recall, the computational power required for any finite language is small -- a deterministic finite state automata is sufficient to process finite languages, I think.

So there is no such thing as context-free languages or recursively enumerable languages, right? Programming languages are not context-free, they are just simple regular languages, right? The idea that a programming language is a context-free language ... well, that's an illusion, right?

Why do we even bother to talk about context-free languages, recursive languages, recursively enumerable languages since inside the (finite) computer everything is just a regular language?

Obviously I am playing devils-advocate here, but I would really like to understand the fallacy of my argument.

Summary of Responses

Thank you very much to all who responded. I have studied your responses carefully. There are so many pearls of wisdom in your responses that I decided to summarize them. If my summary is incorrect, unclear, or missing an important concept, please let me know.

> A computer has a finite memory. There are no computers
> with infinite memory. Therefore the only languages that
> a computer can process are those whose member strings
> are finite.


Responses

A computer's memory is finite, so in its memory it can recognize only finite languages. However, if you would pass an external input to the computer, then it could recognize some infinite languages.

Example: a*b is an infinite language and any string in that language can be recognized, even if the string exceeds the size of the computer's memory. Here's how: pass the string into the computer character by character. If the first character that is passed in is not an "a" then go to an error state. Otherwise, stay in the "a" state until a non-"a" character is input. If the character is not a "b" then go to the error state. Otherwise, go to an accept state. For any characters beyond "b" go to the error state.

Not all infinite languages can be recognized using this technique of feeding the input strings in as external input. In fact, the technique can be used only with regular languages. And even of the regular languages, only some of them can be recognized.

Example: For illustration purposes, suppose the computer has a ridiculously small memory size, say, 2 bytes. Suppose 1 byte is required for each state of a finite state automaton. Then the computer will not be able to recognize this regular language: a*b*c* because at least three byes are needed – one byte for the state that consumes all the a's, a second byte for the state that consumes all the b's, and a third byte for the state that consumes all the c's.

Any finite state automaton that requires more states than there are bytes in the computer's memory cannot be recognized.

Finally, with this technique of feeding arbitrarily long strings into the computer as external input, we would need to find a way around certain technical limitations such as a continuous power supply.

> A computer has a finite memory. Therefore the only languages
> that a computer can process are those whose member strings
> are finite … So there is no such thing as context-free languages
> or recursively enumerable languages, right?


Responses

Consider an infinite language. It consists of strings of arbitrary length. Many strings will be longer than the size of the computer's memory. It is incorrect to say that because a computer can hold in its memory only those strings that are of a certain finite length, the language has only finitely many strings. It is true that any finite subset of a language is regular. But that does not mean that the original language must have been regular.

> A computer has a finite memory. Therefore, in general, a computer
> can only process a finite subset of an infinite language. A finite
> subset of a language is regular. So why don't we simply treat all
> languages used in computers as regular?


Responses

The reason to treat, say, a programming language as context-free is that the context-free grammar tells how to parse the language. If you considered just the subset of programs with length no more than 232, that would be regular but the regular expression would likely consist of millions of individual cases and wouldn't be helpful for parsing the programs.

• You can process arbitrarily long strings with finite memory, i.e. you don't have to store them (but nothing beyond regular). Aug 3, 2013 at 9:48
• Note, it isn't fair to say that there aren't infinite languages, it's only fair to say that nobody has ever needed them. Aug 3, 2013 at 10:05
• You are making the following invalid deduction: because a particular computer can only hold finitely many C programs in its memory, therefore there are only finitely many C programs. In general it is true that any finite subset of a language is regular, but that does not mean that the original language must have been regular, if it was infinite. Aug 3, 2013 at 10:51
• I know it is slightly OT but I remembered this question math.stackexchange.com/questions/946/…. It might also interest you ;) Aug 3, 2013 at 18:20
• You are making a very serious error when you try to discuss the theoretical computers used in computer science and real computers in the same way. Theoretical computers are usually not infinite in size, but they are assumed large enough for any finite computation at hand. Real computers have a fixed size, though clever techniques or money can improve it. CS has (often) not found it useful to worry about whether you have 1MB or 1TB available, so assumes you have enough. Real people who have to buy memory do care. Mar 1 at 6:07

The reason to treat a programming language as context-free is that the context-free grammar tells how to parse the language. If you considered just the subset of C consisting of programs of length no more than $2^{32}$ that would be regular, but the regular expression would likely consist of millions of individual cases, and wouldn't be helpful for parsing the programs. You might not even be able to fit the compiler in memory...

For a simpler example, consider a context free grammar for arithmetical expressions with natural numbers, addition and multiplication.

• E -> {sequence of digits 0-9}
• E -> ( E + E )
• E -> ( E * E )

If you only look at expressions with 500 or fewer symbols, that fragment of the language is regular, but it is much more difficult to describe as a regular language than as a context-free one. Plus, the parse tree for the context-free grammar gives a direct way to evaluate the expressions, while the parse tree for that smaller fragment as a regular language is not likely to help evaluate the expression.

Actually, in the sense of the program, you can make a computer as power as the universal Turing Machine. (In fact, the computer you are on probably is.) More precisely, you can write down explicitly a universal Turing Machine in many of the actual computer languages out there. So in a very real-world sense, there are computer program much more power than any finite automata (the model of computation that recognizes regular langauges).

It is true that a computer has finite memory. This just means that a computer will imitate any Turing machine until it runs out of memory, electric, etc. However any computation that halts takes finite amount of time. So theoretically, one would just need to build a more powerful computer. If a computation does not halt by an idealize Turing machine, neither will it by any real computer no matter how powerful. This does change the fact that your real computer is running the same program as a universal Turing machine.

Morever, you should make a distinction between languages and the model of computation. A language is a string of symbols. A recursive langauge is one decided by a Turing Machine. A recursively enumerable language is one accepted by a Turing machine. For instance, the set $H$ of code $\langle e, f \rangle$ such that the $e^\text{th}$ Turing Machine halts on input $f$ is the recursively enumerable set corresponding to the Halting problem. This is a just a set of numbers! An idea! Why should the fact that real computers have finite memory have any bearing on whether a recursive language or regular language (some infinite set; an abstract idea) should "exists" or not.

To ask whether languages (an abstract notion) exists because of the nature of real computers is not entire well-defined question. Does a recursive language not exists because no existing computer can run long enough to halt? But it will halt eventually. Similarly, one can make huge finite automata that will not halt in anyone's lifetime. It will stop eventually too. Does this mean no regular language exist either because no current device can finish the calculation.

Recursive language and regular languages are just ideas computed by other abstract notions like Turing machines or finite automata. The nature of physical computers don't make ideas real.

There are some interesting points raised here.

The thing about all languages recognizable by a computer being finite is wrong. For example, you can make an interactive program that reads an input string from a user, and your program processes each character in the input stream as it is entered. We can eliminate the need to store the whole input string in memory. This means we can have an arbitrarily long input string. It is also possible to make up an infinite language and a program that recognizes the language. For example, suppose the set of alphabet is $\{0,1\}$. I can make up a language $L = 1^*$. $L$ is infinite, and it is obvious how a recognizer can be programmed. ($L$ here is still regular though.)

It is true, however, that assuming limited memory, every language recognizable is regular simply because you can view all the possible states of the memory as states of a DFA. Obviously there is an unfavorable character of this DFA - the outrageously large number of states. This, in a sense, is a reason why programming languages have control statements other than "if" and "case".

There's no fallacy. In practice everything really is regular (finite). However, you won't get much done if you treat them as such. A DFA for the reasonably long strings of an interesting language will end up having unreasonably many states.

• Thank you for your response. Would you elaborate on "you won't get much done if you treat them as such" please? Do you mean that we can treat a language as, say, a context-free language, even though it is really regular? And by doing so, we can have a simpler implementation? So context-free, recursive, and recursive enumerable languages are just fictitious things we create to make it easier to implement finite automata? Aug 3, 2013 at 10:25
• They are no excuse, if every language of importance were regular, every interesting computational problem would be easy to compute, which is not the case at all.
– sxd
Aug 3, 2013 at 10:29
• As an example why infinite languages are useful: note that that to recognize whether a program is grammatically correct is for most programs not regular furthermore there exists countable infinite valid programs over most languages
– sxd
Aug 3, 2013 at 10:35
• @RogerCostello, do try constructing a DFA for the strings in language generated by $S \to () | (S) | SS$, that are at most 10 symbols long. Non-regular grammars are used because, contrary to what theorists will have you believe, they make your life much easier. Aug 3, 2013 at 11:24

I do not agree with this. Suppose you want to check whether two graphs are isomorphic, or whether a number is prime. A priori you do not know the bound on the number of nodes or on the size of the number, hence we do need infinite languages. This however does not contradict the fact that a computer has finite memory, since a Turing machine always uses a finite amount of memory at any given time, it however can use as much memory as it wants in a finite sense, this is fair since we want to abstract out hardware. This is conform with the idea that even for general computers we assume no a priori bound on the amount of memory it has.

• It's probably safe to say that $10^{80}$ (an estimate of the number of atoms in the observable universe) is an upper bound to the number of nodes or the size of the number. Aug 3, 2013 at 11:14

I think, Carl Mummet's answer hits the point but I'd like to add the practical view because Carl doesn't mention the essence of the practical meaning of (non-)regular languages.

Remember: practice never equals theory. Different from theory, it makes more sense in practice to define language types by their efficency of memory use (to recognize a language), not the possible structure of infinite languages (infinite languages don't even exist in the real world, just think of planned obsolescence of technology, limited life spans etc., finite particles universe, so it won't make even sense to consider inifinite languages in real situations).

After all, no useful programming language is just a context-free language (it wouldn't allow for variables, although regular programming languages with turing-complete semantics exist, for example Iota and Jot or other esoteric programming languages). Useful programming languages are typically context-sensitive needed for productive semantics like namespaces. Of course, you could enumerate all possible warning-free compilable C programs which fit into 1KiB but storing them would take massively more memory, significantly more programs than particles in our universe. This is pratically impossible.

By this argument, regular languages cannot practically achieve the same like non-regular languages, even when limited to finite memory. (Parsers of) Languages of certain size cannot fit into your memory, if you try to recognize them as a regular language since the regular expression will grow large, in the worst case (for totally random words) almost linearly with the number of words in the language! Whereas infinity in practice means finity in theory. But with something like a Linear bounded automaton, you can use finite memory to recognize languages containing exponentially (or more?) words. Of course, regular languages are FAST but without a certain efficiency of memory use you won't be able to detect languages at all in practice!

And practice also tells us, that computers cannot process infinite languages with certain complexity. If the program requires unboundedly growing memory to recognize the language. Except for control systems which are LTI-filters or digital hardware automata, it concerns most interesting infinite languages since with finite memory, you could only compress infinite languages into finite space which is possible for finitely bounded languages as well. You really need infinite memory to make use of the power of parsing infinite languages but then what should be the use for us human of an infinite result, even if it's effectively infinite by the notion of infinity due to very long processing time?

So actually, the set of infinite languages that a computer could really recognize in practice are very limited at all. It can be even doubtful, if any reasonable or good computer software should parse infinite languages since maintenance is a relevant factor (everyhwere) as well as limited lifetime of the CPU.