Recursive grammar
 | 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;[citation needed] otherwise it is called a non-recursive grammar.[citation needed]
For example, 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).[1] All types of grammars in the Chomsky hierarchy can be recursive and it is recursion that allows to produce infinite sets of words.
Properties
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.
See also
References
- ^ Notes on Formal Language Theory and Parsing, James Power, Department of Computer Science National University of Ireland, Maynooth Maynooth, Co. Kildare, Ireland.JPR02
(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.
{{cite book}}: ISBN / Date incompatibility (help) - Maurer, P.M. (1990). "Generating test data with enhanced context-free grammars". IEEE Software. 7 (4): 50–55. doi:10.1109/52.56422.