# Recursive grammar

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**.^{[1]}

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).^{[2]}^{[3]}
All types of grammars in the Chomsky hierarchy can be recursive and it is recursion that allows the production of infinite sets of words.^{[1]}

## Properties[edit]

A non-recursive grammar can produce only a finite language; and each finite language can be produced by a non-recursive grammar.^{[1]}
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.^{[4]}

## References[edit]

- ^
^{a}^{b}^{c}Nederhof, Mark-Jan; Satta, Giorgio (2002), "Parsing Non-recursive Context-free Grammars",*Proceedings of the 40th Annual Meeting on Association for Computational Linguistics (ACL '02)*, Stroudsburg, PA, USA: Association for Computational Linguistics, pp. 112–119, doi:10.3115/1073083.1073104. **^**Notes on Formal Language Theory and Parsing, James Power, Department of Computer Science National University of Ireland, Maynooth Maynooth, Co. Kildare, Ireland.**^**Moore, Robert C. (2000), "Removing Left Recursion from Context-free Grammars",*Proceedings of the 1st North American Chapter of the Association for Computational Linguistics Conference (NAACL 2000)*, Stroudsburg, PA, USA: Association for Computational Linguistics, pp. 249–255.**^**Fleck, Arthur Charles (2001),*Formal Models of Computation: The Ultimate Limits of Computing*, AMAST series in computing,**7**, World Scientific, Theorem 6.3.1, p. 309, ISBN 9789810245009.

P ≟ NP | This theoretical computer science–related article is a stub. You can help Wikipedia by expanding it. |