問題タブ [regular-language]

私は問題を解決するのに問題があります:- それは課題です, 私はそれを解決しました, しかし、それは長すぎて漠然としているようです. 誰か助けてください.

a が偶数個、b が奇数個で、文字セットが {a,b} の文字列の正規表現。

こんな簡単な質問をここに投稿しているような気がしますが、このサイトの知識ベースはすごいです。わかってくれてありがとう。

正規表現の最小ポンピング長（正規言語のポンピング補題に関する）を見つけることに関する質問について：

正規表現R=1011（アルファベット{0,1}上）

この文字列ε（空の文字列）と1011に一致するのはそれだけではありませんか？

編集-私はあまりにも多くのクリーネ閉包を見つめてきました。空の文字列εはこの言語ではありません。

正規言語のプロパティは、言語が有限オートマトン（または正規表現）で表現できる場合、それは正規であり、確かにこれは両方で表現できると述べています。（そして、質問は明らかに私にその言語が正規言語であると信じさせる）

しかし一方で、（非公式に）ポンピング補題は、すべての正規言語にはポンピング長があり、少なくともこの長さのすべての文字列をxyzに分割して、結果に影響を与えることなくyを繰り返すことができると述べています。εは定義上ポンピングできず、1011はポンピングできません（これは問題ではないと思います）。他の文字列が一致しないため、yのインスタンスを削除または追加すると、文字列が受け入れられなくなります/一致しました。

私のロジックのエラーはどこにありますか？

2番目の編集-任意のp>4の答えは、x、y、またはzをϕ（ヌルセット）に設定することで言語をポンピングできます。これを何かと連結すると、ヌルセットになりますか？

名前が示すように、正規表現は正規言語にのみ一致すると考えるかもしれません。しかし、実際に使用する正規表現には、理論上の表現で実装できるかどうかわからないものが含まれています。たとえば、後方参照をどのようにシミュレートしますか？そこで、疑問が生じます。実際に使用する正規表現の理論上の力は何ですか？一致させる方法を考えられます{(a^n)(b^n)|n>=0}か？どう{(a^n)(b^n)(c^n)|n>=0}ですか？

ここで、現代の正規表現は正規言語で表現できるものを超えているというコメントをいくつか見ました。これはどうしてですか？

最新の正規表現のどの機能が正規ではありませんか? 例は役に立ちます。

私はこの練習の問題に困惑しています（マークではありません）：

{wは{a、b}の要素です*：aの数は偶数で、bの数は偶数です}

私はこれを理解できないようです。この場合、0は偶数と見なされます。いくつかの受け入れ可能な文字列：{}、{aa}、{bb}、{aabb}、{abab}、{bbaa}、{babaabba}など

同様の例を実行しましたが、aはプレフィックスである必要があり、答えは（aa）（bb） ですが、この場合は任意の順序にすることができます。

クリーネ閉包（*）、結合（U）、交差（＆）、および連結を使用できます。

編集：これにも問題があります

{wは{0,1}*の要素です：w = 1 ^ r 0 1 ^ s 0いくつかのr、s> = 1}

私はメンバーシップアルゴリズムを研究しており、次のようなこの特定の問題に取り組んでいます:

任意の正規言語 L が与えられたときに、L = L* かどうかを判断するアルゴリズムを示してください。

したがって、私の最初の考えは、L の Kleene スターである L* があり、L = L* かどうかを判断するために、L は正則であるため、L* は定義により、正規言語のファミリは、スター クロージャの下で閉じられています。したがって、L は常に L* と等しくなりますか?

それには間違いなくもっと多くのことがあると感じています。おそらく私が見逃しているものがあるでしょう。どんな助けでも大歓迎です。再度、感謝します。

通常、私たちの作業では、キャプチャまたは一致操作で正規表現を使用します。

ただし、正規表現は、正規表現に一致する正当な文を生成するために (少なくとも手動で) 使用できます。もちろん、一部の正規表現は無限に長い文に一致する場合があります (例: 式 ) .+。

正規表現文生成アルゴリズムを使えば解決できる問題があります。

擬似コードでは、次のように動作します。

私のためにこれを実行するアルゴリズムは何ですか?

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

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

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

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

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

つまり、単語のリストを取得し、少なくともすべての単語 (またはそれ以上) に一致する単純な正規表現を作成したいと考えています。

そのためのアルゴリズムが必要です。つまり、そのアルゴリズムの入力は単語のリストであり、出力は正規表現です。明らかに、いくつかの制限があります。同様に、正規表現は、無限の量の単語に一致する必要がある場合、常により多くの単語に一致し、有限数の単語のみを指定します。または、入力のよりコンパクトな表現が必要になります。または、入力として正規表現と追加の単語のリストを与えることも考えており、それらすべてに一致する正規表現を取得したいと考えています (さらに多くの場合もあります)。いずれにせよ、できるだけ単純な正規表現の構築を試みる必要があります。

それを行うことができるテクニックは何ですか？

かなり誤解していました。正規表現の背後にある一般原則を知っています。私はそれが何であるかを知っています。ほとんどの場合、ある言語の正規表現を手で簡単に思いつくことができます。しかし、私はそれを行うアルゴリズムを探しています。

再び少し異なる定式化：

L を正規言語とする。M_n を n 個の要素を持つ L の有限サブセットとします。M_n を M_(n+1) のサブセットとします。

有限の単語セットを取得して正規表現を出力するアルゴリズム LRE が必要です。そして、私はプロパティを持ちたい:

lim_n->無限 | diff( LRE(M_n), L ) | = 0

補題のポンピングは、言語が規則的でないことを証明するために使用されます。しかし、どのようにして言語が
規則的であると証明できるのでしょうか？特に、

そのような質問に取り組むためのトリックや一般的な手順はありますか？