# 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). –  dtldarek Aug 3 '13 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. –  Karolis Juodelė Aug 3 '13 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. –  Carl Mummert Aug 3 '13 at 10:51
I know it is slightly OT but I remembered this question math.stackexchange.com/questions/946/…. It might also interest you ;) –  Honza Brabec Aug 3 '13 at 18:20

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? –  Roger Costello Aug 3 '13 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 '13 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 '13 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. –  Karolis Juodelė Aug 3 '13 at 11:24
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. –  Karolis Juodelė Aug 3 '13 at 11:14