摘要：The question of the computational complexity of natural language has attracted many
linguists, formal language theory experts, mathematicians, and computer scientists over
the last few decades. To determine the complexity of language, researchers have pointed
out various complex morphological or syntactic constructions. But, the arguments used
to infer from these observations a particular complexity, in particular the position of a
language in Chomsky’s hierarchy, are often fallacious. Although this point has been
noted many times, such arguments continue to flourish in the literature and even in
some computational linguistics courses. The arguments share the same property and
depend upon the same common fallacy. While in some cases it is possible to provide a
correct formal proof of the complexity of a language, in many cases, the constructions
in question cannot be used to demonstrate anything about the complexity of that
language. Nonetheless, even in such cases, there is a core intuition underlying the
arguments that may be interesting. We remind readers of the common fallacy and sketch
how such constructions should be presented and exploited in a rigorous way.
