Incomputer science, agrammar is informally called arecursive grammar if it containsproduction rules that arerecursive, 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 anon-recursive grammar.[1]
For example, a grammar for acontext-free language isleft recursive if there exists a non-terminal symbolA that can be put through the production rules to produce a string withA (as the leftmost symbol).[2][3]All types of grammars in theChomsky hierarchy can be recursive and it is recursion that allows the production of infinite sets of words.[1]
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, astraight-line grammar produces just a single word.
A recursive context-free grammar that contains nouseless rules necessarily produces an infinite language. This property forms the basis for analgorithm that can test efficiently whether a context-free grammar produces a finite or infinite language.[4]
| P ≟ NP | Thistheoretical computer science–related article is astub. You can help Wikipedia byadding missing information. |