資料紹介
計算論への入門 練習問題２．１８◆◆
１．目的
本ドキュメントは、「計算論への入門－オートマトン・言語理論・チューリング機械－ エフェーム・
キンバー カール・スミス（著） 杉原 崇憲 （訳）」の練習問題
2.18
◆◆
の模範解答を記述したも
のである。
２．練習問題
2.18
◆◆
の模範解答
All rights reserved.
【ご注意】該当資料の情報及び掲載内容の不法利用、無断転載・配布は著作権法違反となります。
資料の原本内容
計算論への入門 練習問題２．１８◆◆
１．目的
本ドキュメントは、「計算論への入門－オートマトン・言語理論・チューリング機械－ エフェーム・
キンバー カール・スミス（著） 杉原 崇憲 （訳）」の練習問題 2.18◆◆の模範解答を記述したも
のである。
２．練習問題 2.18◆◆の模範解答
解答：
P28 の定理 2.4.1 における「共通部分」を適用する。
下記の表現図 D を考える。この表現図 D を受理する言語 M は正則である。
表現図 D
Σ
Σ
w
ｓ
ｆ
このとき、L∩M=L'であるから定理 2.4.1 より L'は正則である。（解答終了）
COPYRIGHT（C）2008 トイレその後に. ALL RIGHTS RESERVED.
