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か所の ③ には同じものが入る。）

\usepackage{tikz}
\begin{document}
\begin{tikzpicture}[->, shorten >=1pt, auto, semithick]
  % 定义状态节点
  \node[circle, draw] (s_) at (-2, 0) {$S_-$};
  \node[double,circle, draw] (s0) at (0, 0) {$S_0$};
  \node[circle, draw] (s+) at (2, 0) {$S_+$};

  % 定义状态转移
\path 
(s_) 
edge[loop left] node[left] {
	$\leftarrow, \leftarrow /\leftarrow\leftarrow$,\\
	$\rightarrow,\leftarrow /\epsilon$} ()
edge[bend right] node[below] {3} (s0)
(s0) 
edge[bend right] node[above] {${1}$} (s_)
edge[bend left] node[above] {$\rightarrow, Z / \rightarrow Z$} (s+)
(s+) 
edge[loop right] node[above] {${2}$} ()
edge[bend left] node[below] {${3}$} (s0);

\draw[->] (-0.5, -0.5) -- (s0);

\end{tikzpicture}
\end{document}

遷移規則 $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)で求めたものと同じである。④と⑤を埋めよ。

\usepackage{tikz}
\begin{document}
\begin{tikzpicture}[->, shorten >=1pt, auto, semithick]
  % 定义状态节点
  \node[double, circle, draw] (s0) at (-2, -2) {$S_0$};
  \node[circle, draw] (s0plus) at (-2, 2) {$S_{0+}$};
  \node[circle, draw] (splusplus) at (2, 2) {$S_{++}$};
  \node[circle, draw] (splus0) at (2, -2) {$S_{+0}$};

  % 定义状态转移
  \path 
  % S0+ 到其他节点
  (s0plus) edge[bend left] node[above] {$\to, \uparrow / \to Y \uparrow$} (splusplus)
           edge[bend left] node[right] {3} (s0)
           edge[loop above] node {4} (s0plus)
  % S++ 到其他节点
  (splusplus) edge[bend left] node {$\epsilon, Y / \epsilon$} (s0plus)
              edge[bend left] node[right] {$\epsilon, X / \epsilon$} (splus0)
              edge[loop right] node[right] {5} (splusplus)
  % S+0 到其他节点
  (splus0) edge[bend left] node {3} (s0)
           edge[bend left] node {$\uparrow, \to / \uparrow X \to$} (splusplus)
           edge[loop right] node[right] {2} (splus0)
  % S0 到其他节点
  (s0) edge[bend left] node {$\uparrow, Z / \uparrow Z$} (s0plus)
       edge[bend left] node {$\epsilon, Z / \to Z$} (splus0);

\draw[->] (-3, -3) -- (s0);
\end{tikzpicture}
\end{document}

ヒント：この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つの状態間の状態遷移図のみ示してある。