Up 1.2 記号列の導出  

　一般に，集合Ｅの要素の有限列──空な列εを含める──全体の集合をＥ*で表わし，また，Ｅ+＝Ｅ*−{ε} とおく。Ｅの要素を“記号”と読むとき，Ｅ*の要素を“記号列”と読む。

　記号の集合Ｅと，集合Ｐ⊂Ｅ*×Ｅ*に対し,
“Ｐをプロダクションとする記号列の導出(derivation)”
の概念を，つぎのように定義する。

　即ち，Ｐの要素を“規則(production rule)"と呼び，(φ,ψ)∈Ｐを

φ→ψ

で表わすとき，

  1. 記号列α，βに対し，規則σ→τと記号列γ,δが存在して，

    α＝γσδ，β＝γτδ

    となるとき,“αに規則σ→τを適用して記号列βが直接導出される”と言い，

    α⇒β
    で表わす。
    　また，任意の記号列αに対し，
    α⇒α
    であると約束する。

  2. 記号列α1,α2,････,αmにおいて
    α1⇒α2，α2⇒α3，････,αm-1⇒αm
    であるとき,“α1はαmを導く”と言い，

    α1αm

    で表わす。したがって特に，各記号列αに対し，

    αα
    である。

　なお，→，⇒， がプロダクションＰに対するものであることを明示しようとするときは，


のように書くことにする。