問題タブ [formal-languages]

ここでは回答せず、この質問を にコピーした 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) の「線形時間」で決定できるはずです。複雑さのクラスがたとえば「軽度の文脈依存」なのか「インデックス付き」なのか、まだわかりませんが、おそらく文脈自由と文脈依存の間の何か(?)です。

次の正規表現について考えてみます。

1. 7歳以上
2. （7）+

数学の正規表現理論に精通している人は、2つの正規表現が意味的に同じであることに同意しますか？

言語が決定可能であることを証明するとき、あなたは効果的に何をしていますか？

これに対する答えが「いいえ」であるという数学的な証明さえあるのではないかと思いますが、質問: あるタイプの php のような言語を発明できますか (つまり、舞台裏でコードを評価するいくつかの行と、表示されたhtmlに評価されます)常に適切にネストされる可能性がありますか? 私が話していることの例を挙げると、rails/haml

2 番目の %tr は最初の %tr と垂直方向に揃える必要がありますが (出力 html では兄弟であるため)、各ブロックを開始する行により、1 行追加でインデントされます。インデントが制御構造と適切なネストの両方を反映し、それぞれが競合することなく、ある種の html メタ言語を開発できる可能性はありますか? もしそうなら、そのようなものは存在しますか？

R自明言語とは何ですか? つまり、定義は何ですか？

R自明なモノイドとは何ですか?

コンテキスト: 形式言語。確かに、R-自明な言語はスターフリー言語のサブセットです。

私は主に形式言語とオートマトン理論のバックグラウンドを持っていますが、構文的なモノイドの特徴付けについてはあまり知りません。したがって、そのような言語の小さな例で基本的な定義を示すとよいでしょう。

（QAサイトを置き去りにしたくないため、複数のQAサイトをサポートし、その質問もそこに表示するために、この質問を他のサイトにも投稿しました：cstheory.stackexchange.com、math .stackexchange.com , mathoverflow.net . 一般に、私はクロスポストに反対していますが、この場合、特定の分野の質問の完全な参照になるという同じ目標を持っているため、質問をクロスポストすることが最善の方法ですできるよ。）

基本的に、特定の XSD スキーマを正規表現で置き換えることができるかどうかを知りたいです。XML スキーマ言語は、有効な XML インスタンスのセットが任意のタイプの言語 (コンテキスト依存であっても) である XSD を生成できることを知っています。「正規表現と同等」のスキーマを特定したいと思います。次の問題に取り組んだ後、この質問を思いつきました。

特定のテキスト形式を解析する必要があり、最初に正規表現を試してみたところ、正規表現で十分に解析できることがわかりました。次に、この形式で受信したメッセージの XML 表現を作成したかったので、正規表現グループを XML 要素にマップしました。次に、正規表現の構造に基づいて XSD スキーマを手動で作成しました。最終的に、スキーマから元の正規表現を構築できるという意味で、正規表現を置き換えることができるスキーマができました。逆のこともできました。正規表現からスキーマを自動的に作成します。そのため、メッセージを XML に変換し、同時に検証することができました。私の質問は次のとおりです。

1. すべての正規表現を XSD スキーマで表現できますか? (つまり、XSD スキーマを生成できる正規表現が与えられた場合)

2. 任意の XSD スキーマが与えられた場合、与えられたスキーマを表現する正規表現があるかどうかを判断する方法はありますか?

   編集：おそらく最初の質問への答えはイエスです。なぜなら、特定の正規表現に依存しない方法で正規表現を使用したからです（これはすべての正規表現の証明ではありません）。

I was reading a book named "An introduction to Formal Languages and Automata" by Peter Linz. In one of it's questions, it asked me to, "Design an acceptor for integers in a programming language C" Can some one please tell me how can I obtain an answer for this. Any help would be greatly appreciated

まず第一に、これが私が求めているものの正しい翻訳であるかどうかはわかりません。

私のコースの1つでは、正規表現や形式言語などについて学び始めました。

この場合、私が1Rから始めたとしましょう。そうすれば、1Rまたは0Rのどちらかを続けていくことができます。

1Rから始めると、1 ....すると、文（この場合は2進数）は完全になりますか？後で何かを「追加」できないので、1Rと言ってから、1を選択してから、もう一度1Rを選択しますか？

よろしくお願いします。正しくない場合は、投稿にタグを付け直してください。

追加した：

1100110を生成する方法は？

これは宿題ではなく、パワーポイントからの例/質問です。それがどのように行われるのかわかりません。

そのようなものは存在しますか？もしそうなら、例を挙げていただけますか？ありがとう。

ANTLRにNOTロジックはありますか? 私は基本的に私が持っているルールを否定しようとしていて、それが可能かどうか疑問に思っていました.ANDロジックもありますか?