{{Short description|Computer science and linguistics concept relating to non-terminal production}} In computer science, a grammar is informally called a '''recursive grammar''' if it contains production rules that are recursive, meaning that expanding a non-terminal according to these rules can eventually lead to a string that includes the same non-terminal again. Otherwise it is called a '''non-recursive grammar'''.<ref name="ns02">{{citation | last1 = Nederhof | first1 = Mark-Jan | last2 = Satta | first2 = Giorgio | contribution = Parsing Non-recursive Context-free Grammars | doi = 10.3115/1073083.1073104 | location = Stroudsburg, PA, USA | pages = 112–119 | publisher = Association for Computational Linguistics | title = Proceedings of the 40th Annual Meeting on Association for Computational Linguistics (ACL '02) | year = 2002| doi-access = free }}.</ref>
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).<ref>[http://www.cs.may.ie/~jpower/Courses/parsing/parsing.pdf#search='indirect%20left%20recursion' Notes on Formal Language Theory and Parsing] {{Webarchive|url=https://web.archive.org/web/20170828232456/http://www.cs.may.ie/~jpower/Courses/parsing/parsing.pdf#search='indirect%20left%20recursion' |date=2017-08-28 }}, James Power, Department of Computer Science National University of Ireland, Maynooth Maynooth, Co. Kildare, Ireland.</ref><ref>{{citation | last = Moore | first = Robert C. | contribution = Removing Left Recursion from Context-free Grammars | location = Stroudsburg, PA, USA | pages = 249–255 | publisher = Association for Computational Linguistics | title = Proceedings of the 1st North American Chapter of the Association for Computational Linguistics Conference (NAACL 2000) | url = http://dl.acm.org/citation.cfm?id=974305.974338 | year = 2000}}.</ref> All types of grammars in the Chomsky hierarchy can be recursive and it is recursion that allows the production of infinite sets of words.<ref name="ns02"/>
==Properties== A non-recursive grammar can produce only a finite language; and each finite language can be produced by a non-recursive grammar.<ref name="ns02"/> For example, a straight-line grammar produces just a single word.
A recursive context-free grammar that contains no useless rules necessarily produces an infinite language. This property forms the basis for an algorithm that can test efficiently whether a context-free grammar produces a finite or infinite language.<ref>{{citation|title=Formal Models of Computation: The Ultimate Limits of Computing|volume=7|series=AMAST series in computing|first=Arthur Charles|last=Fleck|publisher=World Scientific|year=2001|isbn=9789810245009|at=Theorem 6.3.1, p. 309|url=https://books.google.com/books?id=c42oYf4zBzMC&pg=PA309}}.</ref>
==References== {{reflist}}
{{formal languages and grammars|state=collapsed}} Category:Formal languages
{{comp-sci-theory-stub}}