文脈自由文法の第２回。まずは、定義の復習。次にその定義の中に含まれる生成規則について。
この文脈自由文法とはこの生成規則を使って、非終端記号をなくし、終端記号に変換する。この過程によって最終的に表される言語が、文脈自由言語である。
次に、この変換過程をどのような順番で行うかという問題。そこで、左から順番に変換を行っていくことを最左導出という。ただし、最左導出だからといって一通りではない。生成規則に選択肢がある場合はいろいろな方法があるからである。
最後に構文木の説明。構文木は生成規則の適用過程を木構造で表したものである。
ここで今日のポイント（余談に近い内容だったけど・・）
木で表すと、葉(leaf)と根(root)は必ず一つのパスでつながる。途中で合流したりするものは木ではない
なるほどねぇ。
最後に構文木が存在する言語と最左導出で得られる言語、通常の導出で得られる言語のクラスは等しい。という定理の証明。
