Formal definition The syntax of grammars In the classic formalization of generative grammars first proposed by Noam Chomsky in the 1950s, a grammar G consists of the following components: A finite set N of nonterminal symbols, that is disjoint with the strings formed from G. A finite set of terminal symbols that is disjoint from N. A finite set P of production rules, each rule of the form where is the Kleene star operator and denotes set union. That is, each production rule maps from one string of symbols to another, where the first string (the "head") contains an arbitrary number of symbols provided at least one of them is a nonterminal. In the case that the second string (the "body") consists solely of the empty string—i.e., that it contains no symbols at all—it may be denoted with a special notation (often , e or ) in order to avoid confusion. A distinguished symbol that is the start symbol, also called the sentence symbol. A grammar is formally defined as the tuple . Such a formal grammar is often called a rewriting system or a phrase structure grammar in the literature. Some mathematical constructs regarding formal grammars The operation of a grammar can be defined in terms of relations on strings: Given a grammar , the binary relation (pronounced as "G derives in one step") on strings in is defined by: the relation (pronounced as G derives in zero or more steps) is defined as the reflexive transitive closure of a sentential form is a member of that can be derived in a finite number of steps from the start symbol ; that is, a sentential form is a member of . A sentential form that contains no nonterminal symbols (i.e. is a member of ) is called a sentence. the language of , denoted as , is defined as the set of sentences built by . Note that the grammar is effectively the semi-Thue system , rewriting strings in exactly the same way; the only difference is in that we distinguish specific nonterminal symbols, which must be rewritten in rewrite rules, and are only interested in rewritings from the designated start symbol to strings without nonterminal symbols. Example For these examples, formal languages are specified using set-builder notation. Consider the grammar where , , is the start symbol, and consists of the following production rules: 1. 2. 3. 4.