終端記号と非終端記号
( Σ ∪ N ) ∗ n ( Σ ∪ N ) ∗ → ( Σ ∪ N ) ∗ {\displaystyle (\Sigma \cup N)^{*}n(\Sigma \cup N)^{*}\rightarrow (\Sigma \cup N)^{*}} ここで n ∈ N {\displaystyle n\in N}
ここで ∗ {\displaystyle {}^{*}} は クリーネのスター(つまり、0個以上の並びを意味する)、 ∪ {\displaystyle \cup } は和集合を表し、よって ( Σ ∪ N ) ∗ {\displaystyle (\Sigma \cup N)^{*}} は0個以上の記号の並びを表す。つまり、左辺は少なくとも1つの非終端記号を含む。右辺が空列の場合は、誤解を避けるために Λ {\displaystyle \Lambda } , e {\displaystyle e} , ε {\displaystyle \epsilon } のような記号を使うことがある。
開始記号 s ∈ N {\displaystyle s\in N}
以上からなる4つ組 < N , Σ , P , s > {\displaystyle <N,\Sigma ,P,s>} として、言語が形式的に定義される。