Chomsky hierarchy
David G. Hays · Encyclopedia of Computer Science · 2003
For the mathematician, an alphabet is a set of symbols and a language is a set, finite or infinite, of strings formed from that alphabet. A grammar is a finite system that characterizes a language. Customarily, grammars work by substitution (i.e. by production). Take the alphabet (or, as it is usually called, the terminal alphabet) of the language VT, add a nonterminal alphabet VN, and a special symbol S that belongs to neither VT, nor VN. A production or rule of substitution, R, is an ordered pair of strings, R = T1 → T2. A grammar is a system, G = 〈 VN, VT, P, S 〉, where P denotes the set of allowable productions. To use the grammar, start with S and find a rule (i.e. a production) S → T1 and substitute T1 for S. Find another rule S1 → T2, such that S1 matches part or all of T1, and substitute T2 for the matched part of T1. Continue with any member of P until the result is a string that contains only terminal symbols. This sequential process is called the derivation of the string, and the final string belongs to the language. The language consists of exactly the strings that can be so derived.