言語理論の検索結果1 - 1 件 / 1件

• あとで読む

  うさぎでもわかるオートマトンと言語理論　第07羽　文脈自由文法

  • 4 users
  • www.momoyama-usagi.com
  • 暮らし
  • 2020/05/31

  こんにちは、ももやまです。 今回はオートマトンと言語理論の中でも重要な文脈自由文法についてまとめていきたいと思います。 前回の記事の内容（Myhill-Nerodeの定理・正則ではない言語の証明法）はこちら↓ www.momoyama-usagi.com １．文脈自由文法とは 文脈自由文法は、以下の4つの要素で構成されるような文法を表します。 （出発記号 \( S \) 以外はすべて集合です。） 非終端記号（変数） \( N \) 後ほど説明する生成規則 \( P \) によって書き換えることができるような文字（記号）の集まりを表します。基本的に \( S \), \( A \), \( B \) などの大文字が使われます。 終端記号 \( \Sigma \) それ以上書き換えることができない文字の集まりです。 生成規則 \( P \) 1文字の終端記号を終端記号と非終端記号が組み合わされ