2025年ｷｮﾀﾞ初め

ｷｮﾀﾞ初めっていつまでやっていいんでしょう。

表記

1. \( \Sigma = \{ \uparrow, \downarrow \} \)とする。
2. \( \Sigma^* \)を\( \Sigma \)の元\( 0 \)文字以上からなる文字列全体の集合とする。
3. \( \Sigma^* \)の元\( s \)が正則であるとは、任意の\( s \)の始切片\( t \)に対して「\( t \)に含まれる\( \uparrow \)の個数が\( \downarrow \)の個数以上である」が成り立つことである。
4. \( \Sigma^* \)の元\( s \)が超正則であるとは、任意の\( s \)の始切片\( t \)に対して「\( t \)に含まれる\( \uparrow \)の個数が\( \downarrow \)の個数超過である」が成り立つことである。
5. \( T \)を\( \Sigma^* \)の正則な元であって\( \uparrow \)で始まり\( \uparrow \)で終わるもの全体の集合とする。

文字列操作ユーティリティ

1. \( s \in \Sigma^* \)に対して、\( \operatorname{Len}(s) \)で\( s \)の長さを表す。

部分文字列

1. \( s \in \Sigma^* \)と整数\( n \)に対し、\( +_s n \in \mathbb{Z} \)を以下で定める:
   1. \( n \geq 0 \)ならば、\( +_s n = n \)である。
   2. そうでなければ、\( +_s n = \operatorname{Len}(s) + n \)である。

1. \( s \in \Sigma^* \)と整数\( -\operatorname{Len}(s) \leq n < \operatorname{Len}(s) \)に対して、\( s[n] \in \Sigma \)を以下で定める:
   1. \( n \geq 0 \)ならば、\( s[n] \)は\( s \)の\( n + 1 \)番目の文字である。
   2. そうでなければ、\( s[n] = s[+_s n] \)である。
2. \( s \in \Sigma^* \)と整数\( n, m \)に対して、\( s[n..m] \in \Sigma^* \)を以下で定める:
   1. \( +_s n \geq \operatorname{Len}(s) \)ならば、\( s[n..m] = \)(空文字列)である。
   2. そうでなくて、\( +_s m < 0 \)ならば、\( s[n..m] = \)(空文字列)である。
   3. そうでなくて、\( +_s n > +_s m \)ならば、\( s[n..m] = \)(空文字列)である。
   4. そうでなくて、\( 0 \leq +_s n \leq +_s m < \operatorname{Len}(s) \)ならば、\( s[n..m] \)は\( s \)の\( n + 1 \)文字目から\( m + 1 \)文字目までの文字列である。
   5. そうでなくて、\( +_s n < 0 \leq +_s m < \operatorname{Len}(s) \)ならば、\( s[n..m] \)は\( s \)の先頭から\( m + 1 \)文字目までの文字列である。
   6. そうでなくて、\( 0 \leq +_s n < \operatorname{Len}(s) \leq +_s m \)ならば、\( s[n..m] \)は\( s \)の\( n + 1 \)文字目から末尾までの文字列である。

1. \( s \in \Sigma^* \)と整数\( n, m \)に対して、\( s[n...m] \in \Sigma^* \)を以下で定める:
   1. \( s[n...m] = s[n..(m-1)] \)である。

例

↑↑↓↑[0]=↑
↑↑↓↑[1]=↑
↑↑↓↑[2]=↓
↑↑↓↑[3]=↑
↑↑↓↑[-1]=↑
↑↑↓↑[-2]=↓
↑↑↓↑[-3]=↑
↑↑↓↑[-4]=↑
↑↑↓↑↓↓↑[2..2]=↓
↑↑↓↑↓↓↑[2..-3]=↓↑↓
↑↑↓↑↓↓↑[2..9]=↓↑↓↓↑
↑↑↓↑↓↓↑[2...-1]=↓↑↓↓

足し算と掛け算

1. \( (s, t) \in \Sigma^* \times \Sigma^* \)に対し、\( s + t \)を\( s \)と\( t \)を連結させたものと定義する。
2. \( (s, n) \in \Sigma^* \times \mathbb{N} \)に対し、\( s \cdot n \)を\( s \)を\( n \)個連結させたものと定義する。
   1. とくに、\( s \cdot 0 =, s \cdot 1 = s \)である。

Reg

1. \( s \in \Sigma^* \)に対し、\( \operatorname{Reg}(s) \)を「\( s \)の末尾に並ぶ\( 0 \)個以上の\( \downarrow \)を全て取り除いたもの」とする。

基本列

\( (s, n) \in T \times \mathbb{N} \)に対し、\( \operatorname{FS}(s, n) \in T \)を以下で定義する:

1. \( s = \uparrow \)ならば、\( \operatorname{FS}(s, n) = \uparrow \)とする。
2. \( s_{-2} = \uparrow \)ならば、\( \operatorname{FS}(s, n) = s[0..-2] + \downarrow\uparrow \cdot n \)である。
3. \( s_{-2} = \downarrow \)ならば、\( s[a..-1] \)が超正則であるような\( a \)が存在するか調べる。
   1. もし存在しないならば、
      1. \( t = s[0...-2] \)とおく。
      2. \( \operatorname{FS}(s, n) = \operatorname{Reg}(t) \)とする。
   2. もし存在するならば、
      1. そのような中で最大の\( a \)を\( b \)とおく。
      2. \( t_1 = s[0...b] \)とする。
      3. \( t_2 = s[b...-1] + \downarrow \)とする。
      4. \( \operatorname{FS}(s, n) = \operatorname{Reg}(t_1 + t_2 \cdot n) \)とする。

証明

任意の\( (s, n) \in T \times \mathbb{N} \)に対し、\( \operatorname{FS}(s, n) \in T \)であることを証明する。そのために補題をいくつか述べるが、証明は読者への演習問題とできるほど簡単なので省略する。

• 補題1: \( s \in \Sigma^* \)が正則であれば、\( s \)の任意の始切片も正則である。
• 補題2: \( s \in \Sigma^* \)が超正則であれば、\( s \)の任意の始切片も超正則である。
• 補題3: \( s, t \in \Sigma^* \)が正則であれば、\( s + t \)も正則である。
• 補題4: \( s \in \Sigma^* \)が超正則、\( t \in \Sigma^* \)が正則であれば、\( s + t \)は超正則である。
• 補題5: \( s \in \Sigma^* \)が正則であれば、任意の\( n \in \mathbb{N} \)に対し、\( s \cdot n \)は正則である。
• 補題6: \( s \in \Sigma^* \)が超正則であれば、任意の\( n \in \mathbb{N} - \{ 0 \} \)に対し、\( s \cdot n \)は正則である。

これらを使用して証明を行う。使用しない補題もあるかもしれない。

1. \( s = \uparrow \)ならば、\( \operatorname{FS}(s, n) = \uparrow \)は正則なのでよい。
2. \( s_{-2} = \uparrow \)ならば、\( s[0...-2] \)が正則であることから、\( s[0..-2] \)は超正則である。そのため、\( n \)による帰納法により容易に従う。
3. \( s_{-2} = \downarrow \)でかつ\( s[a..-1] \)が超正則であるような\( a \)が存在しない場合は、補題1から明らかである。
4. \( s_{-2} = \downarrow \)でかつ\( s[a..-1] \)が超正則であるような\( a \)が存在する場合は、\( t_1 \)と\( t_2 \)はともに正則であるから、\( \operatorname{FS}(s, n) \)は正則である。

階層

\( (s, n) \in T \times \mathbb{N} \)に対し、\( H_s(n) \)を以下で定義する:

1. \( s = \uparrow \)ならば、\( H_s(n) = n \)である。
2. そうでなければ、\( H_s(n) = H_{\operatorname{FS}(s, n)}(n + 1) \)である。

巨大数

\( H_{\uparrow\uparrow\uparrow\uparrow\uparrow\uparrow}(6) \)を「原始数列に巨大数たんのコスプレを着せてみた」とする。