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
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
<templatestyles src="Reflist/styles.css" />
Cite error: Invalid <references> tag; parameter "group" is allowed only.
<references />, or <references group="..." /><templatestyles src="Asbox/styles.css"></templatestyles>
- ↑ 1.0 1.1 1.2 Lua error in package.lua at line 80: module 'strict' not found..
- ↑ Notes on Formal Language Theory and Parsing, James Power, Department of Computer Science National University of Ireland, Maynooth Maynooth, Co. Kildare, Ireland.
- ↑ Lua error in package.lua at line 80: module 'strict' not found..
- ↑ Lua error in package.lua at line 80: module 'strict' not found..
