Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
Recursive grammar
open-in-new
<h2 id="properties">Properties</h2> <p>A non-recursive grammar can produce only a finite language; and each finite language can be produced by a non-recursive grammar.<a class="footnote-ref" id="fnref:5" href="#fn:5"><sup>5</sup></a> For example, a <a href="/facts/Straight-line_grammar/Rn6MxaT8">straight-line grammar</a> produces just a single word. </p><p>A recursive context-free grammar that contains no <a href="/facts/Useless_rules/yu1FFdK4">useless rules</a> necessarily produces an infinite language. This property forms the basis for an <a href="/facts/Algorithm/fnl5NmRt">algorithm</a> that can test efficiently whether a context-free grammar produces a finite or infinite language.<a class="footnote-ref" id="fnref:6" href="#fn:6"><sup>6</sup></a> </p> <h2 id="references">References</h2> <ol> <li id="fn:1"><p>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. <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></p></li> <li id="fn:2"><p>Notes on Formal Language Theory and Parsing, James Power, Department of Computer Science National University of Ireland, Maynooth Maynooth, Co. Kildare, Ireland. <a href="http://www.cs.may.ie/~jpower/Courses/parsing/parsing.pdf#search='indirect%20left%20recursion'" target="_blank">http://www.cs.may.ie/~jpower/Courses/parsing/parsing.pdf#search='indirect%20left%20recursion'</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></p></li> <li id="fn:3"><p>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. <a href="http://dl.acm.org/citation.cfm?id=974305.974338" target="_blank">http://dl.acm.org/citation.cfm?id=974305.974338</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></p></li> <li id="fn:4"><p>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. <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></p></li> <li id="fn:5"><p>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. <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:5" class="footnote-back-ref">↩</a></p></li> <li id="fn:6"><p>Fleck, Arthur Charles (2001), Formal Models of Computation: The Ultimate Limits of Computing, AMAST series in computing, vol. 7, World Scientific, Theorem 6.3.1, p. 309, ISBN 9789810245009. <a href="9789810245009" target="_blank">9789810245009</a> <a href="#fnref:6" class="footnote-back-ref">↩</a></p></li> </ol>