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:
“I will not let him stir
Till I have used the approvèd means I have,
With wholesome syrups, drugs, and holy prayers,
To make of him a formal man again.”
—William Shakespeare (15641616)
“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 (18031882)