Skip to content

Latest commit

 

History

History
17 lines (12 loc) · 775 Bytes

README.md

File metadata and controls

17 lines (12 loc) · 775 Bytes
Raw

Context Free Grammar (CFG)

Formal Definition

A context-free grammar G is a 4-tuple G = (V, Σ, R, S) where:

  1. V is a finite set; each element v ∈ V is called a variable. Each variable represents a different type of phrase or clause in the sentence.
  2. Σ is a finite set of terminals, disjoint from V, which make up the actual content of the sentence. The set of terminals is the alphabet of the language defined by the grammar G.
  3. R is a finite relation in (V × (V ∪ Σ)*). The members of R are called productions of the grammar (symbolized by P).
  4. S is the start variable, used to represent the whole sentence. It must be an element of V.

References