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

, a

grammar In linguistics, grammar is the set of rules for how a natural language is structured, as demonstrated by its speakers or writers. Grammar rules may concern the use of clauses, phrases, and words. The term may also refer to the study of such rul ...

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

Chomsky hierarchy The Chomsky hierarchy in the fields of formal language theory, computer science, and linguistics, is a containment hierarchy of classes of formal grammars. A formal grammar describes how to form strings from a formal language's alphabet that are v ...

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 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 In mathematics and computer science, an algorithm () is a finite sequence of Rigour#Mathematics, mathematically rigorous instructions, typically used to solve a class of specific Computational problem, problems or to perform a computation. Algo ...

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

References

Formal languages {{comp-sci-theory-stub