資料紹介

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

資料の原本内容

計算論への入門 練習問題３．９◆◆
１．目的
本ドキュメントは、「計算論への入門－オートマトン・言語理論・チューリング機械－ エフェーム・
キンバー カール・スミス（著） 杉原 崇憲 （訳）」の練習問題 3.9◆◆の模範解答を記述したもの
である。
２．練習問題 3.9◆◆の模範解答
規則の集合 R について以下に示す。
S→A
S→D
S→e
A→aAb
A→B
A→D
B→aBa
B→C
C→bCa
C→e
D→bDb
D→E
E→bEa
E→e
遷移イメージ

D

E

A

B

e

S
C

e

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

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

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



コメント0件