問題タブ [formal-languages]

以下の言語の左線形および右線形の文法を構築するのに助けが必要ですか？

a）私は以下を持っています：

これは正しいです？b＆cのサポートが必要です。

a と c が偶数回出現し、b が偶数回出現するアルファベット {a,b,c} の文字列を認識できる DFA を作成しようとしています。

これはチューリングマシンや文脈自由言語などの他の数学でしか表現できないのではないかと思っています。

解決策を考えるのは楽しいかもしれません。

特定の言語が通常か、文脈自由か、文脈自由でないかを判断するのに助けが必要です。答えには簡単で非公式な説明で十分なので、ポンピング補題を使用する必要はありません。

私が次の言語を持っているとしましょう：

これが私の解決策です：

L2 は無限のメモリを必要としないため、L2 用に DFA を構築できます。したがって、L2 は規則​​的です。L3 については、上記と同じ理由です。L4 の場合、単純に「abc」を受け​​入れないため、通常の DFA を構築できます。

正規言語は ∩ の下で閉じているため、L1 は正規です。

L2 の場合、言語を次のように分割できます。

L3 に対して DFA を構築できることがわかっているため、L3 は正則です。L4 はコンテキストフリーです。スタックを使用して a:s と b:s の数をカウントする PDA を構築できるからです。

正規言語と文脈自由言語の ∩ が文脈自由言語になるため、L2 は文脈自由です。

L3 の場合、スタックが 1 つに制限されているため、コンテキストフリーではないことがわかります。2 つ以上の比較を行うには、より多くのスタックが必要です。

私の推論は正しいですか？もうすぐ試験があり、この背後にあるアイデアが得られたかどうかを知る必要があります.

前もって感謝します

Context-Free Languages の特定のポンピング レンマの問題について質問があります。

次の言語があるとします。

言語が文脈自由ではないことを証明するための私の試みは次のとおりです。

L は文脈自由であると仮定します。補題から定数 n>0 を取ります。

レンマによれば、Z は Z = uvwxy と書くことができ、次のプロパティが保持されます。

vwxには6つの異なる可能性があります

ここまででいいですか？私が確信していないことは、vwx のさまざまなケースが正しいかどうかです。

前もって感謝します

次の式を評価したい：

βリダクションを使用します。

答えは次のとおりです。

しかし、私は第2段階を理解していません：

ここから：(λx.y)((λz.zz)(λw.w))ここへ(λx.y)((λw.w)(λw.w))

私たちはそこで何をしていますか？私の理解では、α等価ルールを使用する必要があります。

LALR(1) 文法で非終端記号を定義しようとしています (CUP パーサーを使用)。要求される

最終的に、私はこの定義を思いつきました：

はトークンSC間の区切り記号 (セミコロン) でありhour_l、時間のリストの非終端記号です。このソリューションには問題があります。HOURイプシロンは に還元できるため、 が存在しない可能性がありますhour_l。すべての可能性を指定するか、CUP のセマンティック機能を使用するよりも賢い解決策があります (つまり、セクションに何回HOUR存在するかのカウンターを置く)? これを達成するためにセマンティクスを使用しないことをお勧めします。実際、構文に関連しているように思えます。

私は R プログラミングが初めてで、R でテキスト ファイルを読みたいと思っています。

列の 1 つ、列 7 が数値で、各数値が ID を表しているとします。R に数値を文字列のように読み取らせます。そして、各IDがファイルに現れる回数を数えます（後で使用するために、各IDの頻度を特定のIDに割り当てることができるように）私は試しました

これは機能しますが、ID を数字として受け取ります。今、私は試しました

ただし、列 ID 全体を 1 つの文字列として取り、

私は得る

私は CFG を初めて使用し
ます。言語を生成する CFG を作成する際のヒントを教えてください。

例えば

L = {am bn | m >= n}

私が得たものは次のとおりです。

So -> a | aSo | aS1 | e
S1 -> b | bS1 | e

bしかし、 の数が の数よりも多くなる可能性があるため、この領域は間違っていると思いますa。

この問題の解決/証明に問題があります。何かアイデアはありますか？

私はこれについてグーグルで調べましたが、本当に決定的なものは何も表示されませんでした。

A と B の 2 つの言語があるとします。

A = { w は {a,b,c}* のサブセットで、w の最後の文字から 2 番目の文字は b です }

B = { w は、最後の文字が b であるような {b,d}* のサブセットです }

これをどのように定義しますか？アルファベットは両方の結合で {a,b,c,d} になると思いますが、それ以外は、これの DFA を作成する方法がわかりません。

誰かがこれに光を当てることができれば、それは素晴らしいことです.