問題タブ [language-theory]

次の言語は文脈自由ですか?

これを生成するために文脈自由文法を考え出そうとしましたが、できないので、文脈自由ではないと仮定しています。矛盾による私の証明については：

L が文脈自由であると仮定すると、

ポンピング補題によって与えられる定数を p とします。

文字列 S = a^pb^pc^pd^p を選択します。ここで、S = uvwxy

|vwx|として <= p の場合、最大で vwx に 2 つの異なるシンボルを含めることができます。

ケース a) vwx には 1 つのタイプのシンボルのみが含まれているため、uv^2wx^2y は i+s != k+r になります。

ケース b) vwx には 2 種類のシンボルが含まれています。

i) vwx は b と c で構成されているため、uv^2wx^2y は i+s != k+r になります。

ここで私の問題は、vwx が a と b、または c と d のいずれかで構成されている場合、i と k または s と r が一斉に増加して i+s == k になる可能性があるため、それらをポンピングしても言語が壊れる必要はないということです。 +r。

私は何か間違ったことをしていますか、それともこれは文脈自由言語ですか?

Predicates と LINQ について頭を悩ませようとしています。

LINQ の構文は理解できるようになりつつありますが、LINQ の背後にある理論については少し問題があります。

これが私がこれまでに持っているものです。LINQ を設計するとき、LINQ を使用してクエリできるオブジェクトを実装する必要がある各メンバーを定義する新しいインターフェイスを作成する代わりに、Microsoft は代わりに既存のクラス IEnumerable を取得し、拡張メソッドを使用してこのクラスを拡張することにしました。

拡張メソッドを理解していると思います。拡張メソッドは、静的クラス内の静的メソッドです。このメソッドに渡される最初のパラメーターは、thisパラメーターと共に渡され、拡張される型を定義します。次に、拡張メソッドと同じ名前空間内のこの型のインスタンスは、メソッドを利用できます。

そのため、Microsoft は、System.LINQ 名前空間内で IEnumerable を拡張する多数の拡張メソッドを作成しました。System.LINQ 名前空間を使用し、IEnumerable を実装するオブジェクトを含むすべてのクラスは、これらの拡張メソッドを使用してそのオブジェクトをクエリできます。これらの各拡張メソッドは、2 番目のパラメーターとしてデリゲートを受け取ります。

に関してはwhere、 IEnumerable を拡張し、 whereIEnumerable を実装する新しいオブジェクトを返す拡張メソッドです。次のパラメーターwhereは、Func (ジェネリック func) 型の述語 (ブール値を返すメソッド) です。これはデリゲートで、true または false を返し、最大 16 個のパラメーターを受け取ることができます。ただし、この基準を満たすメソッドを記述し、 Func 型のインスタンスを作成してメソッドに向け、この変数をwhereメソッドに渡す必要はなく、C# を使用すると、これをオンザフライで記述できます。LINQ クエリを作成するときに単語の後に置くものはすべてwhere、述語になります。

バックグラウンドで、IEnumerable を実装するオブジェクトのメンバーが繰り返され、述語に対して評価されます。if は、構文trueを使用して新しい IEnumerable オブジェクトに追加されます。yield return

これが少しまとまりがないように見える場合は申し訳ありませんが、基本的に私はそれを理解しているので、基本的にすべてを脳から吐き出しました.ここで何が起こっているのかを正しく理解するのに少し苦労しているので、上で書いたことを一般的に拡張します。

私はLispの方言（Racket）を学び始めたばかりですが、誰かがリンクを持っているかどうか、またはLisp言語のファミリーの理論的基礎を、私が論文、記事、または本を意味するリソースによって示すことができるかどうかを知りたいですあなたが考えることができるものは何でも。

できれば、どの数学的概念を使用して演算子を構築するか、それらをどのように解決するか、恒等式などを統一することを示します。ウィキペディアでSEXPを読んだことがありますが、少し浅いです。

物事がどのように機能するかを他の人に説明できるようにしたいので、私は基礎に興味があります。

前もって感謝します。

私はその問題について考え始めたところです。すべてのC++テンプレートは、クラス（または関数）オブジェクトを返す「通常の」関数に置き換えることができますか？通常はコンパイル時プログラムを意味します。

そのため、C ++コンパイルでのテンプレートのインスタンス化を「通常の関数（コンパイラの解析ツリーなどで動作するコンパイル時プログラムを意味する）」に置き換えたいので、declerative構文は使用しません。

次のアイデアで、C ++のテンプレートメカニズム全体を置き換えることができると思いますか？この方法でテンプレートを理解しやすくなると思いますか？少し理論的な質問ですが、この質問の種類について話し合うのに最適な場所はどこかわかりません。

次の文字列を受け入れる有限オートマトンを描画する必要があります

私の見解 では、文字列がから始まり、空の文字列も含まれているためa(a+b+c)*、これは正規表現である可能性があります。a

今、下の画像のようにFAを描くロジックが見つかりませんでした

質問 1:a FA で文字列が then で始まる場合、読みながらxto に移動します なぜここで読まないのですか?yba

質問 2:なぜ a,b on state のループを使用しy、z

文脈依存の文法を理解しようとしていて、言語が

1. {ww | w は文字列です}
2. {a ⁿ b ⁿ c ⁿ | a、b、cは記号です}

文脈自由ではありませんが、型指定されていないラムダ計算に似た言語が文脈依存であるかどうかを知りたいです。単純だがおもちゃではない例 (上記のおもちゃの例を考えます) の例を見てみたいと思います。たとえば、記号の文字列がは現在スコープ内にあります (たとえば、関数の本体を生成する場合)。文脈依存文法は、未定義/未宣言/未結合の変数を (セマンティックではなく) 構文エラーにするのに十分強力ですか?

「半正規」文法は、次の形式の規則のみを許可する文法です。

ここで、XとYは任意の単一の非終端記号であり、xとyは任意の単一の終端記号です。

たとえば、これは言語a +b+の半正規文法です。

言語が正規言語ではない半正規文法の例を挙げてください。言語が何であるか、そしてなぜそれが規則的でないのかを必ず言ってください。

無限の言語はすべて決定不可能なのだろうか?

TM が無限の言語を決定しようとすると、永久にループするため、決定者ではなく認識者になるため、それらは正しいに違いありません。

みんなありがとう。

では、Java コンパイラのようなものを作成する演習を行います。あまり詳しくは触れません。基本的に、閉じ括弧を識別できる正規表現を使用できるかどうかを知りたいです。たとえば、これは合法的な入力になります

そして、これはありません

ご覧のとおり、2 つのオープナー ({) に対して 1 つのクローザー (}) しかないため、無効な入力になります。正規表現を使用して、出現回数が一致することを識別する方法はありますか?