日々の流転

λ. DCG で a^n b^n c^n (n > 0) という言語を表現できるか?

数日前に水島さんがTwitterで「ところで、 DCG で a^n b^n c^n という言語を表現できます？ (PEG で表現できて CFG で表現できない言語の例 )」と書いていた。 その後の議論は追いかけていないけど、素性の一致を書ける(cf. Haskellでパーサを書く時に面倒な点)くらいだから、そんなのは自明に表現できる。

s --> {N=s(_)}, as(N), bs(N), cs(N).

as(z) --> [].
as(s(N)) --> [a], as(N).

bs(z) --> [].
bs(s(N)) --> [b], bs(N).

cs(z) --> [].
cs(s(N)) --> [c], cs(N).

使用例は以下のような感じ。

?- s([],[]).
No
?- s([a,b,c],[]).
Yes
?- s([a,a,b,c],[]).
No
?- s([a,a,b,b,c,c],[]).
Yes
?- s(X,[]).
X = [a, b, c] ;
X = [a, a, b, b, c, c] ;
X = [a, a, a, b, b, b, c, c, c]
Yes
?-

PrologやDCGについて興味のある方は、向井先生と尾崎先生の「論理プログラミング」講義資料(2004年度)などを参照すると良いかもしれません。

λ. 東方風神録、霊夢TypeBでノーマルクリア

霊夢TypeBでのノーマル初クリア(th10_03.rpy)。 ステージ6は集中力切れた。 けど、マウンテンオブフェイスは初めてとれた。

東方風神録 リプレイファイル情報
Version 1.00a
Name hiro    
Date 07/11/25 15:19
Chara ReimuB 
Rank Normal 
Stage All Clear
Score 38100982
Slow Rate 3.65

λ. PEG意見交換会

PEG意見交換会のUstream.tvでのストリーミングを見たら、ちょうど稲葉さんの発表の途中だった。

「A ← ‘a’ A ‘a’/ ‘a’」が「aaaaa」にマッチしないって、思ってたよりもPEGってだいぶ非直観的なんだな。 あと、ちょっと気になったのは、発表資料に「理論的に『PEGにマッチする例を完全に列挙』は不可能」と書いてあったところ。全ての文脈依存言語は帰納的(recursive)で当然帰納的可算(recursively enumerable)なので、これはつまりPEGでは文脈依存言語でない言語を表現できるということなのだろうか。

【追記】 色々と勘違いしてた。いくらなんでも構文解析は決定可能だろうから、PEGの表す言語は帰納的で、したがって帰納的可算なので、マッチする例を列挙することは可能。それと、文脈依存言語⊂帰納的言語なので、PEGが文脈依存でない言語を表せるかどうかはまた別の問題。