Definition (context-free grammar):
A context-free grammar is a Chomsky grammar G = ( Σ , N , P , S ) {\displaystyle G=(\Sigma ,N,P,S)} such that all productions are of the form
where V ∈ N {\displaystyle V\in N} and α ∈ ( N ∪ Σ ) ( N ∪ Σ ) ∗ {\displaystyle \alpha \in (N\cup \Sigma )(N\cup \Sigma )^{*}} .
Definition (context-free language):
A context-free language is a language L {\displaystyle L} over an alphabet Σ {\displaystyle \Sigma } so that there exists a context-free Chomsky grammar G {\displaystyle G} that accepts precisely L {\displaystyle L} .
Definition (Dyck language):
Let n ∈ N {\displaystyle n\in \mathbb {N} } . The Dyck language D n {\displaystyle D_{n}} of order n {\displaystyle n} is the formal languange
whose alphabet is Σ = { ( 1 , … , ( n , ) 1 , … , ) n } {\displaystyle \Sigma =\{(_{1},\ldots ,(_{n},)_{1},\ldots ,)_{n}\}} .
such that all productions are of the form
,
and 
.
. The Dyck language 
of order 
is the formal languange
.
