Formal grammar

Summary

A formal grammar is a finite set of rewriting rules that produces strings over an alphabet. Starting from a start symbol, one replaces parts of the current string by the rules until only terminal letters remain. The strings obtained in this way form the formal language of the grammar. Grammars give finite descriptions of infinite languages, and restrictions on the form of the rules sort languages into classes of different power.