I know that in an infinite language there are infinite number of strings. I want to know what type of the languages are C, C++ and JAVA? I can have infinite number of variables in all these languages, so I think all these languages are infinite. Please correct me if I am wrong.
$\begingroup$
$\endgroup$
8
-
1$\begingroup$ You are confusing formal language and programming language: a formal language is just an arbitrary set of strings, while a programming language is a tool to write algorithms. $\endgroup$– DenisCommented Sep 2, 2013 at 14:21
-
3$\begingroup$ C, C++ and Java can be viewed as formal languages (or rather, valid programs in said languages under a reasonable encoding), and then they are infinite according to their usual definition. For example, take one program and in the main procedure, add $n$ empty statements ";". $\endgroup$– Yuval FilmusCommented Sep 2, 2013 at 21:13
-
$\begingroup$ @dkuper: How do you reason that a set of strings over a fixed, finite alphabet (as is a programming language) is not a formal language? $\endgroup$– RaphaelCommented Sep 3, 2013 at 7:03
-
$\begingroup$ @Raphael The word language in formal language theory means a set of strings. In programming languages theory, it's a function from strings to semantics (which can either be partial, or map some strings to an error value, but that's an unimportant detail of the formalization). $\endgroup$– Gilles 'SO- stop being evil'Commented Sep 3, 2013 at 9:46
-
$\begingroup$ @Gilles But then, the meaning of "infinite language" retains the same meaning in both ways of reading, doesn't it? $\endgroup$– RaphaelCommented Sep 3, 2013 at 9:48
|
Show 3 more comments
2 Answers
$\begingroup$
$\endgroup$
2
An infinite number of potential identifiers results in an infinite language, but this is a "boring" feature with this consequence, because you can do without. We know that two variables are sufficient to compute any Turing computable function, so this is not the crucial part; I'll assume we use only finitely many variables.
Even then, ignoring real-world constraints such as finite memory, programming languages are -- of course -- infinite languages. Consider the following class of programs:
def m(x) {
x++
x++
...
x++
return x
}
It is clear that you can have as many statements as you want (never mind that, depending on the semantics, it might be that only finitely many of them run without error).
Why do I say "of course"? Well, usually programming languages are supposed to be Turing complete (again, assuming infinite memory). There are infinitely many functions that are Turing computable -- consider only $f_i(x) = i$ for $i \in \mathbb{N}$ -- so we must have infinitely many programs.
It is even so that typical programming languages have infinitely many programs for any single (computable) function! Consider, for instance, $f_1$ and all implementations of the form
def f1(x) {
x++
x++
...
x++
return 1
}
If you think about it, you can do stuff like that -- inserting "meaningless" statements -- in any program written in any language.
-
$\begingroup$ If you get down to it, whether C is Turing-complete is a difficult question. C is actually a family of languages (indexed by limits such as the size of a pointer) such that any computable function can be expressed by sufficiently high-ranking members of the family. C also has no clear notion of “program with a semantic” or even “syntactically correct program”. $\endgroup$ Commented Sep 3, 2013 at 10:20
-
$\begingroup$ @Gilles That's unfortunate, but imho beyond the scope of this site. It is relevant to the question, though, so your comment is appreciated. $\endgroup$– RaphaelCommented Sep 3, 2013 at 10:26
$\begingroup$
$\endgroup$
A language is infinite if and only if it contains arbitrarily long strings. In other word, a language is finite if and only if there is an upper bound on the length of its strings. (Prove it; it's easy. The key assumption is that the language is over a finite alphabet.)
There are several possible definitions for what a language like C means in terms of sets of strings. A reasonable definition would be to consider the set of translation units (that's the C name for an individual source file) that are syntactically correct, but the specification of the C language isn't worded in this way — the closest formal way of stating this is that a C program would be one whose behavior during phase 7 of the translation is defined. Even that is ambiguous since C implementations are allowed to reject programs at compilation time if they provably have no correct execution on that particular implementation. Another possible definition is the set of programs whose semantics is well-defined on all implementations (no undefined behavior).
Continuing the example of C, the standard allows implementations to have limits on many things, including the significant length of an identifier (C99 implementations are allowed to ignore all characters in an identifier after the 63rd), the line length (C99 implementations are allowed to reject source lines longer than 4095 characters), and the length of a string literal (also at 4095 characters). However as far as I know there is no limit on the length of a translation unit, nor any limit on the number of instructions in a block. So you can put as many x++; lines in a function as you like. Or you can simply have as many empty lines as you like — that's enough to show that C is infinite.
Most programming languages are similarly defined with no maximum length on the source file, so they are infinite.
answered Sep 3, 2013 at 10:03
Gilles 'SO- stop being evil'Gilles 'SO- stop being evil'
44k8 gold badges118 silver badges184 bronze badges