Formal Definitions
A context-free grammar G is defined by the 4-tuple:
where
- is a finite set; each element is called a non-terminal character or a variable. Each variable represents a different type of phrase or clause in the sentence. Variables are also sometimes called syntactic categories. Each variable defines a sub-language of the language defined by .
- is a finite set of terminals, disjoint from, which make up the actual content of the sentence. The set of terminals is the alphabet of the language defined by the grammar .
- is a finite relation from to, where the asterisk represents the Kleene star operation. The members of are called the (rewrite) rules or productions of the grammar. (also commonly symbolized by a )
- is the start variable (or start symbol), used to represent the whole sentence (or program). It must be an element of .
Read more about this topic: Context-free Grammar
Famous quotes containing the words formal and/or definitions:
“There must be a profound recognition that parents are the first teachers and that education begins before formal schooling and is deeply rooted in the values, traditions, and norms of family and culture.”
—Sara Lawrence Lightfoot (20th century)
“What I do not like about our definitions of genius is that there is in them nothing of the day of judgment, nothing of resounding through eternity and nothing of the footsteps of the Almighty.”
—G.C. (Georg Christoph)