λx. x K S K @はてな

このブログ内に記載された文章およびコードの著作権は,すべて Keisuke Nakano に帰属します.

Parsing Expression Grammar

以前どこかで「 X\to aXa/\varepsilon という規則が 2^n\quad(n\geq 0) 個の a を受理する」というような記述を見かけた気がして, 確認してみたのですがなかなかうまくいきません. 偶数個の a を受理してしまうという勘違いはなくなったのですが,どう確認しても 2^n-2\quad(n\geq 1) 個 (つまり,0, 2, 6, ... ) の a しか受理しません. X\to aXa/aa なら手許でも 2^n\quad(n\geq 1) 個 (つまり,2, 4, 8, ... ) の a を受理することが確認できました.

その記述を見たのが記憶違いなのか,手許の計算がどこか間違っているのか….