computer science Computer science is the study of computation, automation, and information. Computer science spans theoretical disciplines (such as algorithms, theory of computation, information theory, and automation) to Applied science, practical discipli ...

, a

grammar In linguistics, the grammar of a natural language is its set of structure, structural constraints on speakers' or writers' composition of clause (linguistics), clauses, phrases, and words. The term can also refer to the study of such constraint ...

is informally called a recursive grammar if it contains production rules that are

recursive Recursion (adjective: ''recursive'') occurs when a thing is defined in terms of itself or of its type. Recursion is used in a variety of disciplines ranging from linguistics to logic. The most common application of recursion is in mathematics ...

, 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.. For example, a grammar for a

context-free language In formal language theory, a context-free language (CFL) is a language generated by a context-free grammar (CFG). Context-free languages have many applications in programming languages, in particular, most arithmetic expressions are generated by ...

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). All types of grammars in the

Chomsky hierarchy In formal language theory, computer science and linguistics, the Chomsky hierarchy (also referred to as the Chomsky–Schützenberger hierarchy) is a containment hierarchy of classes of formal grammars. This hierarchy of grammars was described by ...

can be recursive and it is recursion that allows the production of infinite sets of words.

Properties

A non-recursive grammar can produce only a finite language; and each finite language can be produced by a non-recursive grammar. For example, a

straight-line grammar A straight-line grammar (sometimes abbreviated as SLG) is a formal grammar that generates exactly one string.Florian Benz and Timo Kötzing, “An effective heuristic for the smallest grammar problem,” Proceedings of the fifteenth annual conferen ...

produces just a single word. A recursive context-free grammar that contains no

useless rules In formal language theory, a context-free grammar (CFG) is a formal grammar whose Production (computer science), production rules are of the form :A\ \to\ \alpha with A a ''single'' nonterminal symbol, and \alpha a string of Terminal and nonter ...

necessarily produces an infinite language. This property forms the basis for an

algorithm In mathematics and computer science, an algorithm () is a finite sequence of rigorous instructions, typically used to solve a class of specific Computational problem, problems or to perform a computation. Algorithms are used as specificat ...

that can test efficiently whether a context-free grammar produces a finite or infinite language..

References

Formal languages {{comp-sci-theory-stub