計算論への入門 練習問題２．８◆◆
１．目的
本ドキュメントは、「計算論への入門－オートマトン・言語理論・チューリング機械－ エフェーム・キ
ンバー カール・スミス（著） 杉原 崇憲 （訳）」の練習問題 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.