Context-free Grammar - Formal Definitions

Formal Definitions

A context-free grammar G is defined by the 4-tuple:

where

  1. 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 .
  2. 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 .
  3. 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 )
  4. 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:

    “Then the justice,
    In fair round belly with good capon lined,
    With eyes severe and beard of formal cut,
    Full of wise saws and modern instances;
    And so he plays his part.”
    —William Shakespeare (1564–1616)

    “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)