文脈自由文法

(2016/08/22)
  • プログラム言語の殆どを表すことのできるもの

  • 形式文法とも言う
  • 文脈自由文法によって生成される文の集合を文脈自由言語という
  • 定義

  • G=(N, T, P, S)で定義される
  • N
  • 書き換えを行う対象となる非終端記号の集合
  • T
  • 書き換えを行うことができない終端記号の集合
  • P
  • 書き換え(生成)規則の集合
  • S
  • 書き換えを開始する最初の非終端記号
  • 定義
  • G=(N, T, P, S)
  • N={K, S}, T={a, b}, P={S→ε, S→aK, K→bS}
  • ※ εは空列を表す
  • 文法Gによって次のような文が生成(導出)される
  • 1. S→aK→abS→ab
  • 2. S→aK→abS→abaK→ababS→abab
  • 応用情報技術者試験

general(396)