資料紹介

計算論への入門　練習問題３．１４◆◆
１．目的
　本ドキュメントは、「計算論への入門－オートマトン・言語理論・チューリング機械－　エフェーム・
キンバー　カール・スミス（著）　杉原　崇憲　（訳）」の練習問題
3.14
のｂ）◆◆の模範解答を記述
したものである。
２．練習問題
3.14
の
b)
◆◆
の模範解答
...

資料の原本内容

計算論への入門 練習問題３．１４◆◆
１．目的
本ドキュメントは、「計算論への入門－オートマトン・言語理論・チューリング機械－ エフェーム・
キンバー カール・スミス（著） 杉原 崇憲 （訳）」の練習問題 3.14 のｂ）◆◆の模範解答を記述
したものである。
２．練習問題 3.14 の b)◆◆の模範解答
(※この問題は「曖昧でない」文法を見つける問題である。訳者の誤訳と思われる。）
規則の集合 R について以下に示す。
S→aaSb
S→A
A→aAb
A→e

定義（文脈自由文法）
文脈自由文法 G は次により与えられる 4 個組（Σ、NT、R、S）である。
● Σ はアルファベット（終端）
● NT は非終端の集合
● R（規則の集合）は NT×（Σ∪NT）*の部分集合
● S∈NT は初期記号

COPYRIGHT（C）2008 トイレその後に. ALL RIGHTS RESERVED.



コメント0件