問題タブ [regular-language]

私はオートマトン理論の授業を受けており、今はポンピング補題を学んでいます。「L もその補集合も無限の正規部分集合を持たないように言語 L を設計しますか?」という演習問題があります。しかし、私は質問を理解していません。無限正部分集合とは? この要件を満たす言語を見つけるにはどうすればよいですか?

誰でもこの質問に光を当てることができますか?

ありがとう！

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

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

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

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

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

私はオートマトン理論に関する本を読んでいます。この本は、0 と 1 の数が等しい言語が 1*0* と交差すると 1n0n になるという例を示しています。ここで、n > 0 です。

私の質問は、1*0* と交差したときに 1n0n になる正規言語を見つけるにはどうすればよいかということです。それを考える方法はありますか？

更新：答えてくれてありがとう！私が見つけようとしているのは正規の言語だと思うので、1n0n のような言語は機能しません ;) 可能ですか? 何か案は？

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

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

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

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

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

追加した：

1100110を生成する方法は？

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

私はいくつかのテスト準備資料に取り組んでいて、この問題に固執しています。

L = {we {a、b} *：w = wRであり、すべてのaの直後にab}がある場合の文脈自由文法を表示します。

wRは逆にwです。したがって、英語では、すべての「a」の後に「b」が続く回文で、任意の数のaとbを使用します。

これまでのところ、逆の部分でこれを取得しましたが、回文のプロパティが保持されていることを確認しながら、すべてのaの後にabの部分を組み込む方法がわかりません。

どんな助けでも大歓迎です！

ここに宿題の問題があります：

私は L が非正規であることを知っており、Kleene Star がクローズド オペレーションであることを知っているので、L_4 は非正規であると仮定します。

しかし、私の教授は上記の例を提供しました。彼は、が互いに等しいL = {0^p | p is prime}ことを証明することにより規則的であると述べました(この場合、 e は空の単語を意味します)。L*L(000* + e)

したがって、彼の方法には の正規表現を形成することが含まれていまし0^pたが、本質的に既に正規表現を持っている場合、どうすればそれを行うことができるでしょうか?

E = {a, b} とします。L0 = {(b^(n))(a^(2n)) : n >= 0} とします。L = ((NOT OPERATION)L0) とする

L は規則的ですか、文脈自由ですが規則的ではありませんか、それとも文脈自由ではありませんか? あなたの答えを証明してください。

私は L が何であるか、そして L0 が質問でどのように説明されたかと同様の方法でそれを説明する方法と、答えを探しています。

説明は私にとって非常に重要です。貢献したい場合は、具体的にお願いします。テストのためにこの資料を理解しようとしています。

どうもありがとう！

私はリストを持っています：

すべての1,2,3...を「1」、「2」、「3」に置き換え、name1、name2、name3を「name1」、「name」、「name」3に置き換える必要があります。'\n'と'\s'を介してそれを行う方法を知っています。

しかし、もっと良い方法があると思います。誰かがこのように知っていますか？

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

私は、（もしあれば）どの実世界のプログラミング言語が正規文法を持っているかについて興味があります（つまり、構文的に正しいすべてのプログラムのセットが正規です）。

この質問も参照してください：どのプログラミング言語が文脈自由ですか？。