2015 年度[講義]の演習問題

数理コンピュータ科学 I
2015 年度演習問題
水谷正大
a
q0
演習 1 Q = {q0 , q1 , q2 }, Σ = {a, b}, F = {q1 } として、右図で定義され
q1
b
a
b
q2
るオートマトン M1 が受理する言語 L(M1 ) を決定し、これを正
規表現で表しなさい。
a, b
演習 2 正規表現 a(a + b)∗ で表される言語を受理する有限オートマトンを構成しなさい。
0
0
1
1
1
演習 3 右図のような状態 {p0 , p1 } を持つ機械
0
p0
M2 と状態 {q0 , q1 } を持つ機械 M3 が
p1
q0
q1
1
定める言語 L(M2 ) および,L(M3 ) に対
0
して、
L(M2 ) ∪ L(M3 )
L(M2 ) ∩ L(M3 )
を受理する機械をそれぞれ定義しなさ
い。
q0
b
q1
b
q2
演習 4 Q = {q0 , q1 , q2 }, Σ = {a, b}, F = {q2 } とする、
右図で定められる M4 が受理する言語 L(M4 ) を
a, b
決定しなさい。
演習 5 非決定有限オートマトン M = (Q, Σ, δ, q0 , F ) が受理する言語 L(M ) は、L(M ′ ) = L(M )
である等価な決定有限オートマトン M ′ を構成することができる。先の M4 と等価な決定有限オー
トマトン M5 を具体的に与えなさい。
1
演習 6 先の M2 , M3 が受理する言語 L2 = L(M2 ) および L3 = L(M3 ) に対して、
L2 · L3 = {xy | x ∈ L2 , y ∈ L3 }
を受理する有限オートマトン M を構成しなさい。
q0
演習 7 Q = {q0 , q1 , q2 }, Σ = {a, b}, F = {q0 } として、右図で定義され
b
a
ε
るオートマトン M5 と等価な決定有限オートマトンを構成しな
さい。
q1
a
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
を生成するオートマトンを構成しなさい。
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-回
で定めるとする。
2
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,
aB → aa.
BA → AB,
bA → bb,
cB → cc.
P3 :S → aSA | aB,
cA → Ac,
Ac → Bbcc,
BA → bBc,
B → bc.
P4 :S → aSBc | abc,
cB → Bc,
bB → bb.
で定まる文法 G1 , G2 , G3 , G4 は言語
{an bn cn |, n ≥ 1}
を導出することを示しなさい。
演習 11 VN = {S, A, B}, VT = {a, b} として、生成規則
P : S → aSBA | abA,
bA → ba,
AB → BA,
bB → bb,
aA → aa.
が導出する言語を決定しなさい。
演習 12 Σ = {a, b, c} 上の回文（ palindrome）を生成する生成規則を与えなさい。
演習 13 VN = {S, A, B}, VT = {a, b} として、生成規則
S → aA | bS | bB | ε,
A → aaB | bS | ε,
B → aA | bS | ab
が導出する言語を受理する有限オートマトンを構成しなさい。
S
演習 14 右図の機械 M6 が受理する言語を導出する文法を定義しなさい。
a
A
b
B
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)
を計算しなさい。
3

Download Report