「正規表現とオートマトン：JSONオブジェクトの妥当性検証」より：
ウッ、まじい！ "a"でも"b"でもないプロパティ名を許してますが、その他のプロパティがソート順で"a", "b"の後に来るとは限らないので、上の図のワイヤリングではダメですね。
真面目に対処するとノード数が増えるし、プロパティ名の順序付けが効果的に使えないし …
プロパティ名の順序付けを効果的に使って真面目に対処します。ノード数は増えますが、たいしたことはありません。
まず、プロパティ名の出現パターンを普通に表すと (u*. "a"?, v*, "b", w*) となります。ここで、u, v, w はプロパティ名のリテラルではなくて変数です。辞書式順序を不等号「＜」で表すとして次の条件を満たします。
- u ＜ "a"
- "a" ＜ v かつ v ＜ "b"
- "b" ＜ w
(u*. "a"?, v*, "b", w*) という記号列を認識するオートマトンを作ってみれば次のようです。
JSONオブジェクトの認識では、プロパティ"a"の直後に箱X、プロパティ名"b"の直後に箱Y、プロパティ名変数u, v, wの直後に箱Zが付くので、次のようになります。
これでOKです。Zが3箇所にあるのが気になるかもしれません。箱をマクロ展開すると確かに冗長です。でも、関数呼び出しのようにサブオートマトンに入り込んでから出てくるなら、図の上の重複を気にする必要はありません（実際は重複が起きないので）。
3つのZを集約して重複を除くなら、次のようです。
[追記]最後の絵を見ていると、u, v, wを区別する必要はないですね。プロパティ名が辞書式順序で来るのを前提にするなら、u, v, w をまとめて z って1つの変数にして、zに次の条件を付ければ十分です。
- z ≠ "a" and z ≠ "b"
結局、最初の見通しが正しかった、ってことみたい。
単なるワイルカードじゃなくて、(not "a" and not "b") のようなパターンとマッチさせて、プロパティ名がこのパターンにマッチしたら箱Zに遷移する、というやり方で修復できるでしょ、たぶん。
[/追記]
