ここでは回答せず、この質問を にコピーした cstheory.stackexchange で回答してください。
JSON と XML はどちらも文脈自由言語と呼ばれることが多く、主に EBNF の正式な文法によって指定されています。ただし、これはオブジェクト キーの一意性を必要としないRFC 4329 のセクション 2.2で定義されている JSON にのみ当てはまります (多くの人は知らないかもしれませんが、{"a":1,"a":2} は有効な JSON です!)。しかし、JSON で一意のキーが必要な場合や、XML で一意の属性名が必要な場合、これは文脈自由文法では表現できません。しかし、一意のキーを持つ JSON の言語クラスと整形式の XML (一意の属性名を意味する) はどれですか?
このテーマに関して私が見つけた最良の論文の 1 つ (Murato et al, 2001: Taxonomy of XML Schema Languages using Formal Language Theory ) では、キー/キー参照や一意性などの整合性制約が追加レイヤーでチェックされることを明示的に除外しています。これに加えて、XML スキーマまたは DTD によって定義された XML のサブセットはコンテキストフリーです。しかし、すべての整形式 XML 文書の完全なセットではありません。
ネストされたスタック オートマトン (= インデックス付き言語) は、一意のキー制約を使用して JSON を解析できるはずです。XML では、一意の整数のすべてのコンマ区切りリストの言語 S への質問を単純化できます。できれば引用して、もっと知っている人はいますか？
PS:言語を決定する単純なアルゴリズム (文脈自由部分以外) は、優れた並べ替えアルゴリズムに基づいています。したがって、最悪の場合は O(n log n) の「線形時間」で決定できるはずです。複雑さのクラスがたとえば「軽度の文脈依存」なのか「インデックス付き」なのか、まだわかりませんが、おそらく文脈自由と文脈依存の間の何か(?)です。