Formal Grammars
A formal grammar of this type consists of:
- a finite set of production rules (left-hand side right-hand side) where each side consists of a sequence of these symbols
- a finite set of nonterminal symbols (indicating that some production rule can yet be applied)
- a finite set of terminal symbols (indicating that no production rule can be applied)
- a start symbol (a distinguished nonterminal symbol)
A formal grammar defines (or generates) a formal language, which is a (usually infinite) set of finite-length sequences of symbols (i.e. strings) that may be constructed by applying production rules to another sequence of symbols which initially contains just the start symbol. A rule may be applied to a sequence of symbols by replacing an occurrence of the symbols on the left-hand side of the rule with those that appear on the right-hand side. A sequence of rule applications is called a derivation. Such a grammar defines the formal language: all words consisting solely of terminal symbols which can be reached by a derivation from the start symbol.
Nonterminals are usually represented by uppercase letters, terminals by lowercase letters, and the start symbol by . For example, the grammar with terminals, nonterminals, production rules
- ε (where ε is the empty string)
and start symbol, defines the language of all words of the form (i.e. copies of followed by copies of ). The following is a simpler grammar that defines the same language: Terminals, Nonterminals, Start symbol, Production rules
- ε
Read more about this topic: Chomsky Hierarchy
Famous quotes containing the words formal and/or grammars:
“True variety is in that plenitude of real and unexpected elements, in the branch charged with blue flowers thrusting itself, against all expectations, from the springtime hedge which seems already too full, while the purely formal imitation of variety ... is but void and uniformity, that is, that which is most opposed to variety....”
—Marcel Proust (1871–1922)
“A sure proportion of rogue and dunce finds its way into every school and requires a cruel share of time, and the gentle teacher, who wished to be a Providence to youth, is grown a martinet, sore with suspicions; knows as much vice as the judge of a police court, and his love of learning is lost in the routine of grammars and books of elements.”
—Ralph Waldo Emerson (1803–1882)