||This article needs attention from an expert on the subject. The specific problem is: looks like bollocks, but most likely used with different meaning by different authors. (August 2014)|
In computer science, a grammar is informally called a recursive grammar if it contains production rules that are recursive; otherwise it is called a non-recursive grammar.
For example,[improper synthesis?] a grammar for a context-free language is (left-)recursive if there exists a non-terminal symbol A that can be put through the production rules to produce a string with A(as the leftmost symbol). All types of grammars in the Chomsky hierarchy can be recursive and it is recursion that allows to produce infinite sets of words.
A non-recursive grammar can produce only a finite language; and each finite language can be produced by a non-recursive grammar. For example, a straight-line grammar produces just a single word.
A recursive grammar that contains no useless rules necessarily produces an infinite language.
(Relevance of most following references still needs to be established)
About natural language:
- Corballis, Michael (1999). "The Gestural Origins of Language". American Scientist 87 (2): 138. doi:10.1511/1999.2.138.
- Fitch, W. T. (2004). "Computational Constraints on Syntactic Processing in a Nonhuman Primate". Science 303 (5656): 377–380. doi:10.1126/science.1089401. PMID 14726592.
- Premack, David (2004). "Is Language the Key to Human Intelligence?". Science 303 (5656): 318–320. doi:10.1126/science.1093993.
About formal language:
- Cooper, Keith; Linda Torczon (2011). Engineering a compiler (2nd ed.). San Francisco: Morgan Kaufmann. pp. 100–101. ISBN 9780080916613.
- Fitch, W. T.; Friederici, A. D. (2012). "Artificial grammar learning meets formal language theory: an overview". Philosophical Transactions of the Royal Society B: Biological Sciences 367 (1598): 1933–1955. doi:10.1098/rstb.2012.0103.
- Kakde, O. G. (207). Theory of Computation. Firewall Media. pp. 98–99. ISBN 9788131801796.
- Maurer, P.M. (1990). "Generating test data with enhanced context-free grammars". IEEE Software 7 (4): 50–55. doi:10.1109/52.56422.
|P ≟ NP||This theoretical computer science–related article is a stub. You can help Wikipedia by expanding it.|