演習問題の回答例（試験問題を含む）

数理コンピュータ科学 I
2015 年度演習問題の解答例と補足
水谷正大
a
q0
演習 1 Q = {q0 , q1 , q2 }, Σ = {a, b}, F = {q1 } として、右図で定義され
るオートマトン M1 が受理する言語 L(M1 ) を決定し、これを正
q1
b
a
b
q2
規表現で表しなさい。
a, b
[解答例]
語 aba を入力し、δ にしたがい状態遷移を行って到達する状態を考える。
δ(q0 , aba) = δ(δ((q0 , a), ba)
= δ(q1 , ba) = δ(δ(q1 , b), a)
= δ(q0 , a) = q1 ∈ F.
一方で、たとえば語 aaba の入力により到達する状態は以下のようである。
δ(q0 , aaba) = q2 ̸∈ F.
これより、M1 で受理される言語は
L(M1 ) = {a(ba)n | n ≥ 0}
である。正規表現を使って a(ba)∗ と表される。
演習 2 正規表現 a(a + b)∗ で表される言語を受理する有限オートマトンを構成しなさい。
[解答例]
1
a
q0
正規表現 a(a + b)∗ の表す言語は次のようである。
q1
a, b
b
a(a + b)∗ = {a}(a + b)∗
q2
= {a}(a ∪ b)∗
a, b
= {a}({a} ∪ {b})∗
}
{
= {a}{a, b}∗ = ax | x ∈ {a, b}∗ .
つまり、a(a + b)∗ は、先頭が a で始まる任意の 1 文字以上の文
字列である。
0
0
演習 3 右図のような状態 Q2 = {p0 , p1 } を持つ機械 M2
と状態 Q3 = {q0 , q1 } を持つ機械 M3 が定める言
1
p0
0
p1
1
語 L(M2 ) および,L(M3 ) に対して、
1
1
q0
q1
0
L(M2 ) ∪ L(M3 )
L(M2 ) ∩ L(M3 )
を受理する機械をそれぞれ定義しなさい。
[解答例]
M2 は奇数個の 1 を含む語を、M3 は奇数個の 0 を含む語を受理する。したがって、∀w ∈
L(M2 ), L(M3 ) について、|w| ≥ 1 に注意する。したがって、
{
}
L(M2 ) ∪ L(M3 ) = w ∈ {0, 1}∗ | w は 0 を奇数個または 1 を奇数個含む ,
{
}
L(M2 ) ∩ L(M3 ) = w ∈ {0, 1}∗ | w は 0 と 1 とを奇数個ずつ含む
のようになる。
一般の言語 Li を受理する有限オートマントン Mi = (Qi , Σ, δi , q0i , Fi ), (i = 2, 3) を考える（たと
えば、上の左図を M2 、右図を M3 ）
。このとき、次のような有限オートマトン M = (Q, Σ, δ, q0 , F )
を考える。
Q = Q2 × Q3 ,
δ((q 2 , q 3 ), a) = (δ2 (q 2 , a), δ3 (q 3 , a)),
q 2 ∈ Q2 , q 3 ∈ Q3 , a ∈ Σ,
q0 = (q02 , q03 )
受理状態 F として、つぎの 2 つ
{
F =
F∪
F∩
= F2 × Q3 ∪ Q2 × F3
= F2 × F3
2
を選んでおく。このとき、
L(M2 ) ∪ L(M3 ) = 受理状態を F∪ とした M∪ が受理する言語
L(M2 ) ∩ L(M3 ) = 受理状態を F∩ とした M∩ が受理する言語
である。
（証明）
δ(q 2 , q 3 ), ε) = (δ2 (q 2 , ε), δ3 (q 3 , ε)) = (q 2 , q 3 )
に注意して、長さ n 以下の x ∈ Σ∗ について
(
)
δ((q 2 , q 3 ), ax) = δ δ((q 2 , q 3 ), a), x
(
)
= δ (δ2 (q 2 , a), δ(q 3 , a)), x
(
)
= δ2 (δ2 (q 2 , a), x), δ3 (δ3 (q 3 , a), x)
(
)
= δ2 (q 2 , ax)), δ3 (q 3 , ax)
が成立する。したがって、任意の長さの x ∈ Σ∗ に対して
(
)
δ((q 2 , q 3 ), x) = δ2 (q 2 , x), δ3 (q 3 , x) .
となっている。これより、
x ∈ L(M∪ ) ⇔ δ((q02 , q03 ), x) ∈ F∪
⇔ (δ2 (q02 , x), δ3 (q03 , x)) ∈ F∪
⇔ δ2 (q02 , x) ∈ F2 または δ3 (q03 , x) ∈ F3
⇔ L(M2 ) ∪ L(M3 )
一方、
x ∈ L(M∩ ) ⇔ δ((q02 , q03 ), x) ∈ F∩
⇔ (δ2 (q02 , x), δ3 (q03 , x)) ∈ F∩
⇔ δ2 (q02 , x) ∈ F2 かつ δ3 (q03 , x) ∈ F3
⇔ L(M2 ) ∩ L(M3 )
□
いまの場合、F2 = {p1 }, F3 = {q1 } であることから、
{
}
F∪ = (p1 , q0 ), (p1 , q1 ), (p0 , q1 ) ,
{
}
F∩ = (p1 , q1 ) .
この構成から、正規言語は和集合 ∪ および ∩ 演算および（受理集合の役割を変えることによって）
補集合演算について閉じている（再び正規集合になっている）ことが併せて示された。
3
L(M2 ) ∪ L(M3 ) を受理する機械 M∪
0
(p0 , q0 )
L(M2 ) ∩ L(M3 ) を受理する機械 M∩
0
(p0 , q1 )
(p0 , q0 )
(p0 , q1 )
0
1
1
0
1
1
1
0
(p1 , q0 )
1
1
1
0
(p1 , q1 )
(p1 q0 )
(p1 , q1 )
0
0
上記の L(M2 ) ∪ L(M3 ) を受理する機
械は ε-動作付きのオートマトンとして、
0
0
右図にように元のオートマトン M2 と
1
M3 を使って直ちに書き下せる。
s
ε
p0
このオートマトンの構成法は有限オー
1
ε
トマトンと正規表現の同等性を示す際
ε
p1
f
ε
0
に用いられたことを思い出しておこう。
q0
右図において、さらに状態 s から f へ
q1
の ε-動作に加えて f から s へも ε-動作
0
があるオートマトンは言語 (L(M2 ) ∪
1
1
L(M3 ))∗ を受理する。
q0
b
演習 4 Q = {q0 , q1 , q2 }, Σ = {a, b}, F = {q2 } とする、
右図で定められる M4 が受理する言語 L(M4 ) を
a, b
決定しなさい。
[解答例]
a と b からなる文字列で bb で終わるような語の全体 (a + b)∗ bb である。
上の M4 の状態図から、状態遷移は次のようである。
δ(q0 , a) = q0 ,
δ(q0 , b) = {q0 , q1 },
δ(q1 , a) = δ(q2 , a) = ϕ
定義なし
4
q1
b
q2
M4 の動作は、たとえば次のようになる。
δ(q0 , ab) = δ(δ(q0 , a), b) = δ(q0 , b) = {q0 , q1 }
{q0 , q1 } ∩ F = ϕより ab ̸∈ L(M4 ).
δ(q0 , bb) = δ({q0 , q1 }, b) = δ(q0 , b) ∪ δ(q1 , b) = {q0 , q1 , q2 }
{q0 , q1 , q2 } ∩ F ̸= ϕより bb ∈ L(M4 ),
δ(q0 , abb) = δ(δ(q0 , a), bb) = δ(q0 , b) ∪ δ(q1 , b) = {q0 , q1 , q2 }
abb ∈ L(M4 ).
一方、
δ(q0 , abba) = δ({q0 , q1 , q2 }, a) = δ(q0 , a) ∪ δ(q1 , a) ∪ δ(q2 , a) = {q0 }
{q0 } ∩ F = ϕより abba ̸∈ L(M4 ).
演習 5 非決定有限オートマトン M = (Q, Σ, δ, q0 , F ) が受理する言語 L(M ) は、L(M ′ ) = L(M )
であるような等価な決定有限オートマトン M ′ を構成することができる。先の M4 と等価な決定有
限オートマトン M5 を具体的に与えなさい。
[解答例]
M4 は |δ(q0 , b)| = |{q0 , q1 }| = 2 となって非決定である。NFA（非決定有限オートマトン）
M = (Q, Σ, δ, q0 , F ) に対して、DFA（決定有限オートマトン）M ′ = (Q′ , Σ, δ ′ , q0′ , F ′ ) を次のよ
うに構成する。
Q′ = 2Q
δ ′ (p, a) =
∪
(2Q は Q の部分集合全体),
δ(q, a),
q ∈ Q′ , a ∈ Σ,
q∈p
q0′ =
′
q0 ,
F = {r ∈ Q′ | r ∩ F ̸= ϕ}
このとき、次のようにして L(M ) = L(M ′ ) であることがわかる。
x ∈ L(M ) ⇔ δ(q0 , x) ∩ F ̸= ϕ
⇔ δ ′ (q0′ , x) ∩ F ̸= ϕ
⇔ δ ′ (q0′ , x) ∈ F ′
⇔ x ∈ L(M ′ )
M4 の場合、構成すべき決定有限オートマトン M4′ = M5 は次のようになる。
{
}
Q′ = ϕ, {q0 }, {q1 }, {q2 }, {q0 , q1 }, {q0 , q2 }, {q1 , q2 }, {q0 , q1 , q2 } ,
q0′ = q0 ,
{
}
F ′ = {q2 }, {q0 , q2 }, {q1 , q2 }, {q0 , q1 , q2 }
5
δ′
a
b
ϕ
ϕ
ϕ
{q0 }
{q0 }
{q0 , q1 }
{q1 }
ϕ
{q2 }
{q2 }
ϕ
ϕ
{q0 , q1 }
{q0 }
{q0 , q1 , q2 }
{q0 , q2 }
{q0 }
{q0 , q1 }
{q1 , q2 }
ϕ
{q2 }
{q0 , q1 , q2 }
{q0 }
{q0 , q1 , q2 }
以下の機械部品は M5 に含まれる
M4 と等価な決定性有限機械 M5
a
が初期状態 q0 から到達しないの
で実質的には不要（状態図として
非連結成分）。
{q0 }
a
{q1 }
b
{q2 }
a
a
b
{q0 , q1 , q2 }
b
{q0 , q1 }
b
b
b
q
{q0 , q2 }
a, b
a, b
ϕ
a
{q1 , q2 }
演習 6 先の M2 , M3 が受理する言語 L2 = L(M2 ) および L3 = L(M3 ) に対して、
L2 · L3 = {xy | x ∈ L2 , y ∈ L3 }
を受理する有限オートマトン M を構成しなさい。
[解答例]
2 つの構成方法を挙げる。前者は、M2 , M3 から L(M ) = L(M2 ) · L(M3 ) となるような M をつ
くり上げる方法で、正規言語の連接はまた正規言語であることを直接に証明する具体的方法に基づ
いている。後者は、正規表現の立場から ε-動作を使う方法である。
1. Mi = (Qi , {0, 1}, δi , q0i , Fi ), (i = 2, 3) とする（問題に合わせているので添字 i = 2, 3 に注
意）。一般性を失うことなく Q2 ∩ Q3 = ϕ と仮定できる（それぞれ異なる状態名を取るよ
うに変更すればよい）。F2 = {p1 }, F3 = {q1 } である。L2 · L3 を受理する非決定有限機械
NFA M = (Q, Σ, δ, q0 , F ) を次のように構成する。
6
Q = Q2 ∪ Q3 ,
{
{q02 }
q02 ̸∈ F2 のとき
q0 =
{q02 , q03 }
q02 ∈ F2 のとき
F = F3
として、状態遷移関数 δ : 2Q × Σ → 2Q を次のように定める。
δ(q, a) = {δ2 (q, a) | q ∈ Q2 } ∪ {δ3 (q, a) | q ∈ Q3 } ∪ {q03 | q ∈ Q2 かつ δ2 (q, a) ∈ F2 }
このとき、L(M ) = L2 · L3 である。
（証明）まず、L2 · L3 ⊆ L(M ) を示す。x ∈ L2 · L3 とすると、y, z ∈ Σ∗ が存在して
x = yz
y ∈ L2 , z ∈ L3
である。
（a）y = ε のとき、M の定義から、
δ(q0 , z) ∋ δ3 (q03 , z)
となるが、z ∈ L3 より、δ3 (q03 , z) ∈ F3 . これより、δ(q0 , z) ∩ F ̸= F がわかり、
x = εz ∈ L(M ).
（b）y ̸= ε のとき、再び M の定義から
δ1 (q02 , y) ∈ F2
⇒δ(q02 , y) ∋ q03
δ3 (q03 , z) ∈ F3
かつ
かつ
δ(q03 , z) ∈ F
⇒δ(q02 , yz) ∩ F ̸= ϕ
⇒δ(q0 , x) ∩ F ̸= ϕ
これより、x ∈ L(M ) がわかり、L2 · L3 ⊆ L(M ) である。
次に、x = x1 x2 . . . xn ∈ L(M )(n ≥ 0) のとき、x ∈ L2 · L3 を示す。このとき
q0 ∈ Q,
qn ∈ F,
qi+1 ∈ δ(qi , xi )
(0 ≤ i < n)
であるような M の状態列 q0 , q2 , . . . qn ∈ Q が存在する。いま、i を qi ∈ Q3 となる最小の
i とすると、qi = q03 である。
qi ∈ Q3 ⇒
qj ∈ Q3
かつ
δ(qi , xi ) = {δ3 (qi , xi )} (i ≤ j ≤ n)
に注意する。
7
（a）i = 0 のとき、q02 ∈ F2 となって ε ∈ L(M2 ) であるが
δ(qk , xk ) = {δ3 (qk , xk )} (0 ≤ k ≤ n)
より、x ∈ L(M3 ) である. したがって、x = ε · x ∈ L(M2 ) · L(M3 ).
（b）i > 0 のとき、q0 = q02 であり、
δ2 (q02 , x1 . . . xi−1 ) ∈ F2
より、x1 . . . xi−1
∈ L(M2 ) である。一方、δ(q0 , x1 . . . xi−1 ) ∋ q03 である
ことから、δ3 (q03 , xi . . . xn ) ∈ F3 となって xi . . . xn ∈ L(M3 ).
これより、
x = x1 . . . xi−1 xi . . . xn ∈ L(M2 ) · L(M3 ).
以上から L(M ) = L(M2 ) · L(M3 ) である。この構成から、正規言語は連接において閉じて
□
いることが示された。
具体的な構成は以下のようになる。
1
Q = {p0 , p1 , q0 , q1 },
p0
0
q0 = {p0 },
p1
0
q1
1
1
F = {q1 }
1
M の遷移関数の定義から、
δ(p0 , 1) = {p1 , q0 },
0
0
δ(p1 , 0) = {p1 , q0 }
q0
1
と非決定性機械となることに注意しよう。求める
0
M の状態図は右図である。
2. ε-動作付きの構成は簡単である。M2 と M3 を直列に並べ、M2 の受理状態を開放して p2 か
ら、M3 の初期状態 q0 に問題 3 の解答例にあるように ε-動作させて M を次のように構成
する。
0
0
0
1
p0
p1
ε
q0
1
q1
0
1
1
q0
演習 7 Q = {q0 , q1 , q2 }, Σ = {a, b}, F = {q0 } として、右図で定義され
b
a
ε
るオートマトン M5 と等価な決定有限オートマトンを構成しな
さい。
a
8
q1
a, b
q2
[解答例]
ε-動作付き非決定有限オートマトン ε-NFA N = (Q, Σ, δ, q0 , F ) の状態遷移関数は δ : 2Q × {Σ ∪
{ε} → 2Q である。状態集合 R ⊆ 2Q について、ε-動作でのみ到達できる状態集合を E(R) とす
る。ただし、E(R) は R の要素も含むとする。
E(R) = {q| ∈ Q| q は R の要素、または R から ε-動作だけで到達できる状態 }
L(N ) を認識する DFA M = (Q′ , Σ, δ ′ , q0′ , F ′ ) を次のように構成する。
Q′ = 2Q ,
δ ′ (R, a) =
∪
(R ⊆ 2Q )
E(δ(r, a)),
r∈R
q0′ =
′
E(q0 ),
F = {f ∈ Q′ | f ∩ F ̸= ϕ}.
今の場合、ε-NFA M5 から構成すべき DFA M ′ = M5 は次のようになる。
{
}
Q′ = ϕ, {q0 }, {q1 }, {q2 }, {q0 , q1 }, {q0 , q2 }, {q1 , q2 }, {q0 , q1 , q2 } ,
q0′ = E(q0 ) = {q0 , q2 },
{
}
F ′ = {q0 }, {q0 , q1 }, {q0 , q2 }, {q0 , q1 , q2 }
δ′
a
b
ϕ
ϕ
ϕ
{q0 }
ϕ
{q1 }
{q1 }
{q1 , q2 }
{q2 }
{q2 }
{q0 , q2 }
ϕ
{q0 , q1 }
{q1 , q2 }
{q1 , q2 }
{q0 , q2 }
{q0 , q2 }
{q1 }
{q1 , q2 }
{q0 , q1 , q2 }
{q2 }
{q0 , q1 , q2 }
{q0 , q1 , q2 }
{q1 , q2 }
M5 と等価な決定性有限機械 M ′
a, b
ϕ
a
b
{q0 }
b
{q1 }
b
b
a
{q0 , q1 }
a, b
a
{q2 }
a
{q0 , q2 }
{q1 , q2 }
a
{q0 , q1 , q2 }
b
b
9
a
状態 {q0 } および {q0 , q1 } む向かう矢印がないため、これを状態図から取り去ることができる。M5
と等価な簡約化した決定性有限機械 M5′
a
{q0 , q2 }
a
{q2 }
b
b
b
b
ϕ
a, b
a
a
{q1 }
{q1 , q2 }
{q0 , q1 , q2 }
a
b
演習 8 Σk = {0, 1, . . . , k −1} とする。数列 (an )n≥0 が k-automatic 列であるとは、出力付きオー
トマトン M = (Q, Σk , δ, q0 .∆, τ ) が存在して、入力整数 n ≥ 0 の k-進表示文字列 [n]k = w ∈ Σ∗k
について
an = τ (δ(q0 , w))
が成立するときである。Thue-Morse 列 (tn )n≥0
{
tn =
0 文字列 [n]2 内の 1 の数が偶数
1 otherwise
を生成するオートマトンを構成しなさい。
[解答例]
Q = {q0 , q1 }, Σ2 = {0, 1} として、状態遷移関数 δ : Q × Σ2 → Q を
δ(q0 , 0) = q0 ,
δ(q0 , 1) = q1 ,
δ(q1 , 0) = q1 ,
δ(q1 , 1) = q0
で与え、この出力関数 τ : Q → ∆ を
τ (q0 ) = 0,
τ (q1 ) = 1
とした出力付き FA (Q, Σ2 , δ, q0 , {0, 1}, τ ) を考える。目的の Thue-Morse 列 (tn )n≥0 は、この機
械に入力整数 n ≥ 0 の 2-進表示 [n]2 を最上位ビットから読み込ませて得られる出力である。
tn = τ (δ(q0 , [n]2 ).
10
右図で、q0 /0 および q1 /1 は、状態 q0 および q1 の
出力がそれぞれ 0 と 1 であることを表している。
n
[n]2
偶奇
tn
0
0
e
0
1
1
o
1
2
10
o
1
3
11
e
0
4
100
o
1
5
101
e
0
6
110
e
0
7
111
o
1
8
1000
o
1
9
1001
e
0
10
1010
e
0
11
1011
o
1
12
1100
e
0
0
0
1
q0 /1
q1 /1
1
0
1
A/+1
0
演習 9 Q = {A, B, C, D}, Σ2 = {0, 1}, τ (A) = τ (B) = +1,τ (C) =
1
τ (D) = −1 として右図で定義される automatic 列 (fn )n≥1
が 2-folding 列に一致することを確かめなさい。ただし、
(w1 w2 . . . wm )R = wm wm−1 . . . w1 として、列 w ∈ {+1, −1}∗
B/+1
D/-1
0
0
C/-1
に対する折り畳み操作 a ∈ {+1, −1} に関する折り畳み写像
Fa : {+1, −1}∗ → {+1, −1}∗ を
0
Fa (w) = (w, a, wR )
としたとき、2-folding 列 f = (fn )n≥1 を
f = lim F1 ◦ · · · ◦ F1 (ε)
{z
}
k→∞ |
k-回
で定めるとする。
[解答例]
省略
11
1
演習 10 非終端記号 VN 、終端記号 VT 、開始記号 S および生成規則 P に関する文法 G =
(VN , VT , S, P ) において、VN = {S, A, B, C}, VT = {a, b, c} として、生成規則
P1 :S → abc | aAbc,
bB → Bb,
Ab → bA,
aB → aaA,
P2 :S → aSAB | abB,
bB → bc,
Ac → Bbcc,
aB → aa.
BA → AB,
bA → bb,
cB → cc.
P3 :S → aSA | aB,
cA → Ac,
BA → bBc,
B → bc.
P4 :S → aSBc | abc,
cB → Bc,
bB → bb.
で定まる文法 G1 , G2 , G3 , G4 はどれも、言語
{an bn cn |, n ≥ 1}
を導出することを示しなさい。
[解答例] この文法は文脈依存文法である。生成規則 P1 について示す。
S ⇒ abc ◁
S ⇒ aAbc ⇒ abAc ⇒ abBbc2 ⇒ aBbc2 ⇒ a2 b2 c2 ◁
∗
⇒ a2 Ab2 c2 = a2 Abbc2 ⇒ a2 bAbc2 ⇒ a2 b2 Acc ⇒ a2 bbBbc3 ⇒ a2 bBbbc3
⇒ a2 Bb2 c2 ⇒ aaBb3 c3 ⇒ a3 b3 c3 . ◁
∗
∗
∗
⇒ a3 Ab3 c3 ⇒ a3 Bb4 c4 ⇒ a4 b4 c4 ◁
∗
∗
⇒ ak Abk ck ⇒ ak Abbk−1 ck ⇒ ak bAbk−1 ck ⇒ ak bk Ack = ak bkAcck−1 = ak bk Bbck+1
∗
⇒ ak Bbk+1 ck+1 ⇒ ak+1 bk+1 ck+1 ◁
∗
⇒ ak+1 Abk+1 ck+1
演習 11 VN = {S, A, B}, VT = {a, b} として、生成規則
P : S → aSBA | abA,
bA → ba,
AB → BA,
bB → bb,
aA → aa.
が導出する言語を決定しなさい。
[解答例]
12
生成規則 P は文脈異存で、言語 {ak bk ak | k ≥ 1} を導出する。
S ⇒ abA ⇒ aba
S ⇒ aSBA ⇒ aabABA ⇒ aabaBA×
⇒ aabBAA ⇒ aabbAA ⇒ aabbaA ⇒ aabbaa
∗
S ⇒ aSBA ⇒ a
. . a} S (BA) . . . (BA) = ak−1 S(BA)k−1
| .{z
|
{z
}
k−1
⇒a
k−1
k−1
k−1
abA(BA)
⇒ a bA(BA)k−1 ⇒ ak b(AB)k−1 A
k
⇒ ak b(BA)k−1 A ⇒ ak bB(AB)k−2 A2 ⇒ ak b2 (AB)k−2 A2
∗
⇒ ak b2 (BA)k−2 A2 ⇒ ak bk Ak = ak bk−1 bAAk−1 ⇒ ak bk aAk−1
∗
⇒ ak bk aAAk−2 ⇒ ak bk a2 Ak−2 ⇒ ak bk ak .
演習 12 Σ = {a, b, c} 上の回文（ palindrome）を生成する生成規則を与えなさい。
[解答例]
回文 w = x1 x2 . . . xn とは、wR = xn . . . x2 x1 としたとき w = wR である語である。文法
G = ({S}, {a, b, c}, S, P ) において、{a, b, c} 上の回文集合は文脈自由な生成規則
P :
S → aSa | bSb | cSc | a | b | c | ε
で生成される。任意個数のアルファベット集合 Σ = でも同様である。実際、次の導出
∗
S → ε を適用
∗
S → y ∈ Σ を適用
S ⇒ x1 . . . xk Sxk . . . x1 ⇒ w = x1 . . . xk xk . . . x1
S ⇒ x1 . . . xk Sxk . . . x1 ⇒ w = x1 . . . xk yxk . . . x1
によって、偶数または奇数個の文字からなる任意長の回文 w を生成することができる。
演習 13 VN = {S, A, B}, VT = {a, b} として、生成規則
S → aA | bS | bB | ε,
A → aaB | bS | ε,
B → aA | bS | ab
が導出する言語を受理する有限オートマトンを構成しなさい。
[解答例]
正則文法から非決定有限機械 NFA の状態図への変換は次のような対応として取り扱う。
13
正規文法
ε-NFA 部品への対応
S
開始記号 S
S を初期状態にセット
A
A→ε
状態 A が受理状態
A
A → aB
A
A→a
a
a
B
C
受理状態 C を導入
A
A → ab
a
b
D
E
状態 D, E を導入、E を受理状態
与えられた生成規則を上記表の対応で状態図化したののが下図である。新しく状態 C, D,E を導
入しているが、E として既存の S を選んでもよい。
b
a
S
A
b
b
a
a
b
B
C
a
a
b
D
E
S
a
演習 14 右図の機械 M6 が受理する言語を導出する文法を定義しなさい。
A
b
B
[解答例]
M6 で受理される言語は正規表現 ab(a + b)∗ 、つまり ab で始まる任意の文字列
{
}
L(M6 ) = w ∈ {a, b} | w = abx, x ∈ {a, b}∗
である。
問題 13 の解答例に与えた正規文法と ε-NFA 状態図への変換表を逆に読む。ab(a + b)∗ を導出
する正規文法 G = ({S, A, B}, {a, b}, S, P ) は
P :
S → aA,
A → bB,
B → ε | aB | bB
である。
14
a, b
演習 15 Ackermann 関数 A : N × N → N を
A(0, y) = y + 1
A(x + 1, 0) = A(x, 1)
A(x + 1, y + 1) = A(x, A(x + 1, y))
で定義する。A(x, y) は原始帰納関数ではないが、計算することは可能である。A(1, y), A(2, y), A(3, y), A(4, y)
を計算しなさい。
[解答例]
A(1, y) = A(0, A(1, y + 1)) = A(1, y − 1) + 1
= A(0, A(1, y − 2)) + 1 = A(1, y − 2) + 2
...
= A(1, 0) + y = y + 2 ◁
A(2, y) = A(1, A(2, y − 1)) = A(2, y − 1) + 2
= A(1, A((2, y − 2)) + 2 = A(2, y − 2) + 4
...
= A(2, 0) + 2y = A(1, 1) + 2y
= 2y + 3 ◁
A(3, y) = A(2, A(3, y − 1)) = 2A(3, y − 1) + 3
(
)
= 2A((2, A(3, y − 2)) + 3 = 2 2A((3, y − 2) + 3) + 3
(
)
= 22 2A(3, y − 3) + 3 + 3(2 + 1) = 23 A(3, y − 3) + 3(22 + 2 + 1)
...
= 2y A(3, 0) + 3(2y−1 + · · · + 22 + 21 + 1) = 2y A(3, 0) + 3(2y − 1)
= 8 · 2y − 3 = 2y+3 − 3 ◁
A(4, y) = A(3, A(4, y − 1)) = 23+A(4,y−1) − 3
(
)
3+A(4,y−1)
3+A(4,y−2)
−3
= 23+ 2
− 3 = 22
−3
2...
2
3+A(4,0)
= 2| {z }
4
...2
2
...2
− 3 = 2| 2{z } −3 = 2| 2{z } −3
y
y
y+3
ここで power tower 記法
x...
xx
x
x ↑↑ k ≡ x
| {z }
k
を使うと、
A(4, y) = 2 ↑↑ (y + 3) − 3
と表される。
15

Download Report