R06-C-問2

問2

アルファベット $\Sigma = \{\rightarrow, \leftarrow, \uparrow, \downarrow\}$ 上の文字列 $a = a[1]a[2]\cdots a[n]$（各 $i$ に対し $a[i] \in \Sigma$）に対し、2次元ベクトルの系列 $f(a) = (p[0], p[1], \dots, p[n])$（各 $i$ に対し $p[i] = (x[i], y[i])$, $x[i], y[i]$ は整数）を次のように定義する：

$$p[i] = \begin{cases} p[i-1] + (1, 0) & \text{if } a[i] = \rightarrow \\ p[i-1] - (1, 0) & \text{if } a[i] = \leftarrow \\ p[i-1] + (0, 1) & \text{if } a[i] = \uparrow \\ p[i-1] - (0, 1) & \text{if } a[i] = \downarrow \end{cases}$$

すなわち、$f(a)$ は、原点からスタートして $a$ の矢印の向きに従って2次元格子点上を遷移したときの軌跡を表す。
また、各 $i = 1, 2, \dots, n$ に対し、$|x[i]| + |y[i]| > |x[i-1]| + |y[i-1]|$ のとき（$a[i]$ によって原点から遠ざかる方向に遷移したとき） $i$ を前進ステップ、そうでないとき（$a[i]$ によって原点に近づく方向に遷移したとき） $i$ を後進ステップと呼ぶ。

文字列 $a$ が往復的であることを、任意の後進ステップ $i$ に対し、

$$i_0 = \max\{j \mid j \leq i-1, p[j] = p[i-1], j \text{ は前進ステップ}\}$$

が存在し、$p[i] = p[i_0 - 1]$ が成り立つことと定義する。すなわち，往復的な文字列 $a$ に おいては，後進ステップ i による $p[i − 1]$ から $p[i]$ への遷移は，i に対応する前進ステッ プ $i_0$ による $p[i_0 − 1]$ から $p[i_0]$ への遷移を逆にたどるものとなっている．往復的で $f(a)$ の最後の要素が原点であるような文字列 a からなる言語

言語 $L$ を以下のように定義する：

$$L = \bigcup_{n \geq 0} \{a \in \Sigma^n \mid a \text{ は往復的}, p = f(a), p[n] = (0, 0)\}.$$

について，次の各問いに答えよ.

1. 以下の文字列 $a_1, a_2, a_3, a_4$ が $L$ の要素であるか否かをそれぞれ判定せよ。
   • $a_1 = \uparrow \uparrow \downarrow \rightarrow \downarrow \uparrow \leftarrow \downarrow$
   • $a_2 = \rightarrow \rightarrow \leftarrow \leftarrow \leftarrow \uparrow \downarrow \rightarrow$
   • $a_3 = \downarrow \leftarrow \uparrow \rightarrow$
   • $a_4 = \leftarrow \uparrow \uparrow \downarrow \leftarrow \rightarrow \downarrow \leftarrow \downarrow \uparrow$
2. 次の図は、アルファベットを $\{\rightarrow, \leftarrow\}$ に限定した言語 $L \cap \{\rightarrow, \leftarrow\}^*$ を最終状態によって受理するプッシュダウンオートマトン（PDA）の状態遷移図の一部である。空欄 ①, ②, ③ を埋めよ。（2か所の ③ には同じものが入る。）

遷移規則 $a,b / s$ は，遷移元の状態で読んだ入力文字が $a$，スタックの先頭文字が $b$ のとき，遷移先の状態に遷移し，スタックの先頭を文字 $b$ から文字列 $s$ に置き換える動作を表す．ただし，$\epsilon$ は空文字列を表す．初期状態では，スタックは，空であることを表す特殊文字 $Z$ のみを保持しているとする．$S_0$ は初期状態であり唯一の最終状態でもある．
ヒント：状態 $S_0$，$S_+$，$S_−$ は，それぞれ，$x[i] = 0$，$x[i] > 0$，$x[i] < 0$ であることを表す

3. 次の図は、言語 $L$ を最終状態で受理するPDAの状態遷移図の一部である。ただし、②と③は、(2)で求めたものと同じである。④と⑤を埋めよ。

ヒント：このPDAは、$x[i]$ と $y[i]$ の全ての符号の組に対応する9個の状態を持つ。このうち、$x[i] = y[i] = 0$ を表す状態 $S_0$（初期状態であり唯一の最終状態でもある）、$x[i] = 0, y[i] > 0$ を表す状態 $S_{0+}$、$x[i] > 0, y[i] = 0$ を表す状態 $S_{+0}$、$x[i] > 0, y[i] > 0$ を表す状態 $S_{++}$ の4つの状態間の状態遷移図のみ示してある。