資料紹介
計算論への入門 練習問題２．８◆◆
１．目的
本ドキュメントは、「計算論への入門－オートマトン・言語理論・チューリング機械－ エフェーム・キ
ンバー カール・スミス（著） 杉原 崇憲 （訳）」の練習問題
2.8
◆◆
の模範解答を記述したもので
ある。
練習問題
2.8 (
◆◆
模範解答
All rights reserved.
【ご注意】該当資料の情報及び掲載内容の不法利用、無断転載・配布は著作権法違反となります。
資料の原本内容
計算論への入門 練習問題２．８◆◆
１．目的
本ドキュメントは、「計算論への入門－オートマトン・言語理論・チューリング機械－ エフェーム・キ
ンバー カール・スミス（著） 杉原 崇憲 （訳）」の練習問題 2.8◆◆の模範解答を記述したもので
ある。
練習問題 2.8◆◆(模範解答)
a) { (u#,v#) | u,v ∈ {a,b}* , |u|=|v| }
Q2
Q1
a,b
ｑ
ｓ
a,b
#
a,b
ｚ
#
ｐ
a,b,#
ｒ
#
a,b
ｆ
#
ｔ
a,b,#
COPYRIGHT（C）2008 トイレその後に. ALL RIGHTS RESERVED.
b){ ( ambn# , akbn#) | n,m,k ≧ 0 }
a
Q1
a
Q2
q1
b
ｓ
a,b
#
#
b
q2
b
p1
a
p2
#
b
a
q3
#
a
#
q5
q4
#
b
#
a,b
a,b
q6
p3
a,b,#
#
ｆ
a,b,#
COPYRIGHT（C）2008 トイレその後に. ALL RIGHTS RESERVED.
c){ ( anbm#,akbn# ) | n,m,k≧0 }
Q2
Q1
b
ｓ
p1
a
b
b,#
a
q1
#
b,#
#
ｆ
a
a
p2
#
q2
a,b
a,b,#
COPYRIGHT（C）2008 トイレその後に. ALL RIGHTS RESERVED.
