文脈自由文法の標準形について。標準形とは単純化のことで、無用な記号をのぞき、ε規則を除去し、単位規則を除去するというもの。
しかし、話を聞いていると、確かに一つ一つの規則は単純化されるが、規則がかなり増えてしまう。これじゃ意味がないと思っていたけど、チョムスキーの標準形というのを聞いて、これはこれで意味があるのかもしれないと思った。
Gは文脈自由文法(CFG)で、L(G)はεを生成しないとすると、あるG1:CFGがあり、L(G) = L(G1)、A,B,C ∈ V, a∈Tで、
G1の規則はA→BC, A→aの形のみ
つまり、どんなCFGもA→BC, A→aの形にもっていけるという。確かにきれいかもしれない。
ちなみにチョムスキーとは今までの日記にもあったチョムスキーと同じ人物のこと。
最後にチューリング機械の説明をちょこっと。機械の説明よりもチューリングの自転車の話の方が長かったような。
チューリングが乗っている自転車は鍵をかけなくても絶対に盗られないという。なぜなら、その自転車は一部のギアの突起が欠けているため、普通に漕ぐとチェーンが外れてしまうからである。
で、チューリングはそのギアの突起の部分だけで自転車を漕いでいたという。
・・・チューリングは奇人だったという話らしいです。
