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]
YouTube Encyclopedic
-
1/3Views:59011 08316 365
-
Recursive Grammars Solution - Intro to Computer Science
-
7.1: Intro to Session 7: Context-Free Grammar - Programming with Text
-
Left Recursion & Left Factoring Removal
Transcription
For this question, we need to determine if the given grammar generates infinitely many strings starting from the nonterminal word. So we can start from either substitution rule. If we start from the first one, then we end up with 1 possible word. If we start from the second word, then we get the letter a, and then we can insert another word. This can be udacity, so then we end up with audacity. We can do the same thing but twice. So we have a, then instead of going to udacity, we do a again, and then we do udacity. The way this is breaking down kind of looks like this. It should be pretty clear that we can continue this forever and eventually end with udacity. So we can have an arbitrary number of a's, followed by udacity. This inidicates that this grammar generates an infinite number of possible words. In this grammar, we can see that every word begins with a root and then a tail. So what we're going to do to see how many strings this generates is, go through every possible root there can be and then every tail there can be. So root can be uda and also boda. Tail can go directly to cious and city. But we should also look at this substitution rule that has root going directly to tail. So you could have a word that's really the same as tail tail, which adds 2 more possible combinations to what root can be. This gives us 4 possibilites for root and 2 possibilities for tail, which means 8 possibilities all together. This grammar can generate 8 different words. We know that 8 < infinity, so this grammar does not generate an infinite number of words. So here we have a grammar that looks a lot like our first one. However, let's still work it out to see if there's an infinite number of words. So according to problem, we start with word. And there's only 1 substitution rule for word. >From pre udacious, we have 2 options. We could go to super udacious, which gives us one complete word, or we can do pre super udacious. You might have already noticed that we can keep substituting the pre with pre super, and we can keep doing this forever, and stopping at any point and ending with some number of supers followed by udacious. This grammar generates an infinite number of strings.
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
- ^ 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, vol. 7, World Scientific, Theorem 6.3.1, p. 309, ISBN 9789810245009.
This page was last edited on 16 April 2020, at 05:16