API tools faq
paste
Advertisement
SiroKuro

東方巨大数2「橙数」

SiroKuro
Mar 18th, 2018
176
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 13.03 KB | None | 0 0
raw download clone embed print report
  1. ■ 橙数
  2. -------------------------
  3.  
  4. ■ 定義
  5.  
  6. 自然数mとnについて、集合Cと関数Tを次のように定義する。
  7.  
  8. C(0,n)=「終端記号 n 個以下、チョムスキー標準形の生成規則 n 個以下で構成される文脈自由文法」の集合
  9. C(m,n)=「終端記号 T(m-1,n) 個以下、チョムスキー標準形の生成規則 T(m-1,n) 個以下で構成される文脈自由文法」の集合
  10. ※ただし、生成規則に以下のものは含めない。
  11. ・無用な記号(開始記号から到達不能な記号)
  12. ・ε規則(A -> ε の形式で表される記号長 0 の生成規則)
  13. ・単位規則(A -> B の形式で表される、単純な非終端記号の置換)
  14. ※生成規則 0 個の文法 C には含めない。
  15.  
  16. T(0,n)=C(0,n)の要素が生成する構文木の個数の総和
  17. ※ただし構文木は記号長が n^n を超えた時点で生成を打ち切るものとする
  18. T(m,n)=C(m,n)の要素が生成する構文木の個数の総和
  19. ※ただし構文木は記号長が T(n-1,m)^T(m-1,n) を超えた時点で生成を打ち切るものとする
  20.  
  21. このときグラハム数Gについて、T(G,G) の計算結果である自然数を『橙数』とする。
  22.  
  23.  
  24. ■ 計算過程とその考察
  25.  
  26. 自然数mとnが小さい場合について、実際に計算してみる。
  27. なお、終端記号は英小文字a,b,c...、非終端記号は英大文字A,B,C...、非終端記号のうち開始記号としてAを用いる。
  28.  
  29. 例:
  30. m=2, n=2 のとき、
  31. C(0,2) = [
  32. { A -> AA, A -> a },
  33. { A -> AA, A -> b },
  34. { A -> AB, B -> a },
  35. { A -> AB, B -> b },
  36. { A -> BA, B -> a },
  37. { A -> BA, B -> b },
  38. { A -> BB, B -> a },
  39. { A -> BB, B -> b },
  40. { A -> a, A -> b },
  41. { A -> a }
  42. { A -> b }
  43. ]
  44. 生成される構文木は、
  45. { A -> AA, A -> a } => 157個
  46. (((AA)A)A)A
  47. (((AA)A)A)a
  48. (((AA)A)a)A
  49. (((AA)A)a)a
  50. (((AA)a)A)A
  51. (((AA)a)A)a
  52. (((AA)a)a)A
  53. (((AA)a)a)a
  54. ((A(AA))A)A
  55. ((A(AA))A)a
  56. ((A(AA))a)A
  57. ((A(AA))a)a
  58. ((AA)(AA))A
  59. ((AA)(AA))a
  60. ((AA)(Aa))A
  61. ((AA)(Aa))a
  62. ((AA)(aA))A
  63. ((AA)(aA))a
  64. ((AA)(aa))A
  65. ((AA)(aa))a
  66. ((AA)A)(AA)
  67. ((AA)A)(Aa)
  68. ((AA)A)(aA)
  69. ((AA)A)(aa)
  70. ((AA)a)(AA)
  71. ((AA)a)(Aa)
  72. ((AA)a)(aA)
  73. ((AA)a)(aa)
  74. ((Aa)(AA))A
  75. ((Aa)(AA))a
  76. ((Aa)A)(AA)
  77. ((Aa)a)(AA)
  78. ((a(AA))A)A
  79. ((a(AA))A)a
  80. ((a(AA))a)A
  81. ((a(AA))a)a
  82. ((aA)(AA))A
  83. ((aA)(AA))a
  84. ((aA)A)(AA)
  85. ((aA)a)(AA)
  86. ((aa)(AA))A
  87. ((aa)(AA))a
  88. ((aa)A)(AA)
  89. ((aa)a)(AA)
  90. ((aa)a)a
  91. (A((AA)A))A
  92. (A((AA)A))a
  93. (A((AA)a))A
  94. (A((AA)a))a
  95. (A(A(AA)))A
  96. (A(A(AA)))a
  97. (A(AA))(AA)
  98. (A(AA))(Aa)
  99. (A(AA))(aA)
  100. (A(AA))(aa)
  101. (A(Aa))(AA)
  102. (A(a(AA)))A
  103. (A(a(AA)))a
  104. (A(aA))(AA)
  105. (A(aa))(AA)
  106. (AA)((AA)A)
  107. (AA)((AA)a)
  108. (AA)((Aa)A)
  109. (AA)((Aa)a)
  110. (AA)((aA)A)
  111. (AA)((aA)a)
  112. (AA)((aa)A)
  113. (AA)((aa)a)
  114. (AA)(A(AA))
  115. (AA)(A(Aa))
  116. (AA)(A(aA))
  117. (AA)(A(aa))
  118. (AA)(a(AA))
  119. (AA)(a(Aa))
  120. (AA)(a(aA))
  121. (AA)(a(aa))
  122. (Aa)((AA)A)
  123. (Aa)((AA)a)
  124. (Aa)(A(AA))
  125. (Aa)(a(AA))
  126. (a((AA)A))A
  127. (a((AA)A))a
  128. (a((AA)a))A
  129. (a((AA)a))a
  130. (a(A(AA)))A
  131. (a(A(AA)))a
  132. (a(AA))(AA)
  133. (a(AA))(Aa)
  134. (a(AA))(aA)
  135. (a(AA))(aa)
  136. (a(Aa))(AA)
  137. (a(a(AA)))A
  138. (a(a(AA)))a
  139. (a(aA))(AA)
  140. (a(aa))(AA)
  141. (a(aa))a
  142. (aA)((AA)A)
  143. (aA)((AA)a)
  144. (aA)(A(AA))
  145. (aA)(a(AA))
  146. (aa)((AA)A)
  147. (aa)((AA)a)
  148. (aa)(A(AA))
  149. (aa)(a(AA))
  150. (aa)(aa)
  151. (aa)a
  152. A(((AA)A)A)
  153. A(((AA)A)a)
  154. A(((AA)a)A)
  155. A(((AA)a)a)
  156. A((A(AA))A)
  157. A((A(AA))a)
  158. A((AA)(AA))
  159. A((AA)(Aa))
  160. A((AA)(aA))
  161. A((AA)(aa))
  162. A((Aa)(AA))
  163. A((a(AA))A)
  164. A((a(AA))a)
  165. A((aA)(AA))
  166. A((aa)(AA))
  167. A(A((AA)A))
  168. A(A((AA)a))
  169. A(A(A(AA)))
  170. A(A(a(AA)))
  171. A(a((AA)A))
  172. A(a((AA)a))
  173. A(a(A(AA)))
  174. A(a(a(AA)))
  175. a
  176. a(((AA)A)A)
  177. a(((AA)A)a)
  178. a(((AA)a)A)
  179. a(((AA)a)a)
  180. a((A(AA))A)
  181. a((A(AA))a)
  182. a((AA)(AA))
  183. a((AA)(Aa))
  184. a((AA)(aA))
  185. a((AA)(aa))
  186. a((Aa)(AA))
  187. a((a(AA))A)
  188. a((a(AA))a)
  189. a((aA)(AA))
  190. a((aa)(AA))
  191. a((aa)a)
  192. a(A((AA)A))
  193. a(A((AA)a))
  194. a(A(A(AA)))
  195. a(A(a(AA)))
  196. a(a((AA)A))
  197. a(a((AA)a))
  198. a(a(A(AA)))
  199. a(a(a(AA)))
  200. a(a(aa))
  201. a(aa)
  202. aa
  203. { A -> AA, A -> b } => 157個
  204. (((AA)A)A)A
  205. (((AA)A)A)b
  206. (((AA)A)b)A
  207. (((AA)A)b)b
  208. (((AA)b)A)A
  209. (((AA)b)A)b
  210. (((AA)b)b)A
  211. (((AA)b)b)b
  212. ((A(AA))A)A
  213. ((A(AA))A)b
  214. ((A(AA))b)A
  215. ((A(AA))b)b
  216. ((AA)(AA))A
  217. ((AA)(AA))b
  218. ((AA)(Ab))A
  219. ((AA)(Ab))b
  220. ((AA)(bA))A
  221. ((AA)(bA))b
  222. ((AA)(bb))A
  223. ((AA)(bb))b
  224. ((AA)A)(AA)
  225. ((AA)A)(Ab)
  226. ((AA)A)(bA)
  227. ((AA)A)(bb)
  228. ((AA)b)(AA)
  229. ((AA)b)(Ab)
  230. ((AA)b)(bA)
  231. ((AA)b)(bb)
  232. ((Ab)(AA))A
  233. ((Ab)(AA))b
  234. ((Ab)A)(AA)
  235. ((Ab)b)(AA)
  236. ((b(AA))A)A
  237. ((b(AA))A)b
  238. ((b(AA))b)A
  239. ((b(AA))b)b
  240. ((bA)(AA))A
  241. ((bA)(AA))b
  242. ((bA)A)(AA)
  243. ((bA)b)(AA)
  244. ((bb)(AA))A
  245. ((bb)(AA))b
  246. ((bb)A)(AA)
  247. ((bb)b)(AA)
  248. ((bb)b)b
  249. (A((AA)A))A
  250. (A((AA)A))b
  251. (A((AA)b))A
  252. (A((AA)b))b
  253. (A(A(AA)))A
  254. (A(A(AA)))b
  255. (A(AA))(AA)
  256. (A(AA))(Ab)
  257. (A(AA))(bA)
  258. (A(AA))(bb)
  259. (A(Ab))(AA)
  260. (A(b(AA)))A
  261. (A(b(AA)))b
  262. (A(bA))(AA)
  263. (A(bb))(AA)
  264. (AA)((AA)A)
  265. (AA)((AA)b)
  266. (AA)((Ab)A)
  267. (AA)((Ab)b)
  268. (AA)((bA)A)
  269. (AA)((bA)b)
  270. (AA)((bb)A)
  271. (AA)((bb)b)
  272. (AA)(A(AA))
  273. (AA)(A(Ab))
  274. (AA)(A(bA))
  275. (AA)(A(bb))
  276. (AA)(b(AA))
  277. (AA)(b(Ab))
  278. (AA)(b(bA))
  279. (AA)(b(bb))
  280. (Ab)((AA)A)
  281. (Ab)((AA)b)
  282. (Ab)(A(AA))
  283. (Ab)(b(AA))
  284. (b((AA)A))A
  285. (b((AA)A))b
  286. (b((AA)b))A
  287. (b((AA)b))b
  288. (b(A(AA)))A
  289. (b(A(AA)))b
  290. (b(AA))(AA)
  291. (b(AA))(Ab)
  292. (b(AA))(bA)
  293. (b(AA))(bb)
  294. (b(Ab))(AA)
  295. (b(b(AA)))A
  296. (b(b(AA)))b
  297. (b(bA))(AA)
  298. (b(bb))(AA)
  299. (b(bb))b
  300. (bA)((AA)A)
  301. (bA)((AA)b)
  302. (bA)(A(AA))
  303. (bA)(b(AA))
  304. (bb)((AA)A)
  305. (bb)((AA)b)
  306. (bb)(A(AA))
  307. (bb)(b(AA))
  308. (bb)(bb)
  309. (bb)b
  310. A(((AA)A)A)
  311. A(((AA)A)b)
  312. A(((AA)b)A)
  313. A(((AA)b)b)
  314. A((A(AA))A)
  315. A((A(AA))b)
  316. A((AA)(AA))
  317. A((AA)(Ab))
  318. A((AA)(bA))
  319. A((AA)(bb))
  320. A((Ab)(AA))
  321. A((b(AA))A)
  322. A((b(AA))b)
  323. A((bA)(AA))
  324. A((bb)(AA))
  325. A(A((AA)A))
  326. A(A((AA)b))
  327. A(A(A(AA)))
  328. A(A(b(AA)))
  329. A(b((AA)A))
  330. A(b((AA)b))
  331. A(b(A(AA)))
  332. A(b(b(AA)))
  333. b
  334. b(((AA)A)A)
  335. b(((AA)A)b)
  336. b(((AA)b)A)
  337. b(((AA)b)b)
  338. b((A(AA))A)
  339. b((A(AA))b)
  340. b((AA)(AA))
  341. b((AA)(Ab))
  342. b((AA)(bA))
  343. b((AA)(bb))
  344. b((Ab)(AA))
  345. b((b(AA))A)
  346. b((b(AA))b)
  347. b((bA)(AA))
  348. b((bb)(AA))
  349. b((bb)b)
  350. b(A((AA)A))
  351. b(A((AA)b))
  352. b(A(A(AA)))
  353. b(A(b(AA)))
  354. b(b((AA)A))
  355. b(b((AA)b))
  356. b(b(A(AA)))
  357. b(b(b(AA)))
  358. b(b(bb))
  359. b(bb)
  360. bb
  361. { A -> AB, B -> a } => 8個
  362. (((AB)B)B)B
  363. (((AB)B)B)a
  364. (((AB)B)a)B
  365. (((AB)B)a)a
  366. (((AB)a)B)B
  367. (((AB)a)B)a
  368. (((AB)a)a)B
  369. (((AB)a)a)a
  370. { A -> AB, B -> b } => 8個
  371. (((AB)B)B)B
  372. (((AB)B)B)b
  373. (((AB)B)b)B
  374. (((AB)B)b)b
  375. (((AB)b)B)B
  376. (((AB)b)B)b
  377. (((AB)b)b)B
  378. (((AB)b)b)b
  379. { A -> BA, B -> a } => 8個
  380. B(B(B(BA)))
  381. B(B(a(BA)))
  382. B(a(B(BA)))
  383. B(a(a(BA)))
  384. a(B(B(BA)))
  385. a(B(a(BA)))
  386. a(a(B(BA)))
  387. a(a(a(BA)))
  388. { A -> BA, B -> b } => 8個
  389. B(B(B(BA)))
  390. B(B(b(BA)))
  391. B(b(B(BA)))
  392. B(b(b(BA)))
  393. b(B(B(BA)))
  394. b(B(b(BA)))
  395. b(b(B(BA)))
  396. b(b(b(BA)))
  397. { A -> BB, B -> a } => 1個
  398. aa
  399. { A -> BB, B -> b } => 1個
  400. bb
  401. { A -> a, A -> b } => 2個
  402. a
  403. b
  404. { A -> a } => 1個
  405. a
  406. { A -> b } => 1個
  407. b
  408. よって T(0,2) = 352
  409.  
  410. 次に C(1,2) として、生成規則 T(0,2) = 352 以下の文脈自由文法を列挙する必要があるが、以下、割愛する
  411.  
  412. これら計算過程の中で、
  413.  
  414. C(0,n)は、条件に当てはまる全ての文脈自由文法を列挙すればよく、有限集合となる。
  415. T(0,n)は、その計算にあたり構文木を成長させていくが、構文木の上限を設定しているため有限時間内に全構文木を列挙可能であり、計算可能関数である。
  416.  
  417. 以下、同様に
  418. C(1,n)を作成 → T(1,n)を計算 →
  419. C(2,n)を作成 → T(2,n)を計算 → ... →
  420. C(m,n)を作成 → T(m,n)を計算
  421. という手順をたどることで、任意の自然数 m と n について、T(m,n)の値を計算可能である。
  422.  
  423. 以上.
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!