Editing Context-free grammar (section)

== Formal definitions ==
A context-free grammar {{mvar|G}} is defined by the 4-[[tuple]] <math>G = (V, \Sigma, R, S)</math>, 
where{{efn|The notation here is that of {{harvtxt|Sipser|1997|p=94}}. {{harvtxt|Hopcroft|Ullman|1979|p=79}} define context-free grammars as 4-tuples in the same way, but with different variable names.}}
# {{mvar|V}} is a finite set; each element <math> v\in V</math> is called ''a nonterminal 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 {{mvar|G}}.
# {{math|Σ}} is a finite set of ''terminal''s, disjoint from {{mvar|V}}, which make up the actual content of the sentence. The set of terminals is the alphabet of the language defined by the grammar {{mvar|G}}.
# {{mvar|R}} is a finite [[Binary relation|relation]] in <math>V\times(V\cup\Sigma)^{*}</math>, where the asterisk represents the [[Kleene star]] operation. The members of {{mvar|R}} are called the ''(rewrite) rule''s or ''production''s of the grammar. (also commonly symbolized by a {{mvar|P}})
# {{mvar|S}} is the start variable (or start symbol), used to represent the whole sentence (or program). It must be an element of {{mvar|V}}.

=== Production rule notation ===
A [[Formal grammar#The syntax of grammars|production rule]] in {{mvar|R}} is formalized mathematically as a pair <math>(\alpha, \beta)\in R</math>, where <math>\alpha \in V</math> is a nonterminal and <math>\beta \in (V\cup\Sigma)^{*}</math> is a [[string (computer science)|string]] of variables and/or terminals; rather than using [[ordered pair]] notation, production rules are usually written using an arrow operator with <math>\alpha</math> as its left hand side and {{math|''β''}} as its right hand side:
<math>\alpha\rightarrow\beta</math>.

It is allowed for {{math|''β''}} to be the [[empty string]], and in this case it is customary to denote it by {{math|ε}}. The form <math>\alpha\rightarrow\varepsilon</math> is called an ε-production.{{sfn|Hopcroft|Ullman|1979|pp=90–92}}

It is common to list all right-hand sides for the same left-hand side on the same line, using | (the [[vertical bar]]) to separate them. Rules <math>\alpha\rightarrow \beta_1</math> and <math>\alpha\rightarrow\beta_2</math> can hence be written as <math>\alpha\rightarrow\beta_1\mid\beta_2</math>. In this case, <math>\beta_1</math> and <math>\beta_2</math> are called the first and second alternative, respectively.

=== Rule application ===
For any strings <math>u, v\in (V\cup\Sigma)^{*}</math>, we say {{mvar|u}} directly yields {{mvar|v}}, written as <math>u\Rightarrow v\,</math>, if <math>\exists (\alpha, \beta)\in R</math> with <math>\alpha \in V</math> and <math>u_{1}, u_{2}\in (V\cup\Sigma)^{*}</math> such that <math>u\,=u_{1}\alpha u_{2}</math> and <math>v\,=u_{1}\beta u_{2}</math>. Thus, {{mvar|v}} is a result of applying the rule <math>(\alpha, \beta)</math> to {{math|''u''}}.

=== Repetitive rule application ===
For any strings <math>u, v\in (V\cup\Sigma)^{*}, </math> we say {{mvar|u}} ''yields'' {{mvar|v}} or {{mvar|v}} is ''derived'' from {{mvar|u}} if there is a positive integer {{mvar|k}} and strings <math>u_{1}, \ldots, u_{k}\in (V\cup\Sigma)^{*}</math> such that <math>u = u_{1} \Rightarrow u_{2} \Rightarrow \cdots \Rightarrow u_{k} = v</math>.  This relation is denoted <math>u ~\stackrel{*}{\Rightarrow}~ v</math>, or <math>u\Rightarrow\Rightarrow v</math> in some textbooks.  If <math>k\geq 2</math>, the relation <math>u ~\stackrel{+}{\Rightarrow}~ v</math> holds. In other words, <math>(\stackrel{*}{\Rightarrow})</math> and <math>(\stackrel{+}{\Rightarrow})</math> are the [[reflexive transitive closure]] (allowing a string to yield itself) and the [[transitive closure]] (requiring at least one step) of <math>(\Rightarrow)</math>, respectively.

=== Context-free language ===
The language of a grammar <math>G = (V, \Sigma, R, S)</math> is the set
: <math>L(G) = \{ w\in\Sigma^{*} : S ~\stackrel{*}{\Rightarrow}~ w\}</math>
of all terminal-symbol strings derivable from the start symbol.

A language {{mvar|L}} is said to be a context-free language (CFL), if there exists a CFG {{mvar|G}}, such that <math>L=L(G)</math>.

[[Pushdown automaton#PDA and context-free languages|Non-deterministic pushdown automata]] recognize exactly the context-free languages.