問題タブ [formal-languages]

通常の言語は、操作の下で閉じられます。

init(L) = ある x に対して wx が L にあるような文字列 w の集合。

編集: x は、任意の文字列、文字、または空の文字列にすることができます。どうすればそれを証明できますか?

誰かがスタック トランスレータの仕組みを説明できますか? 主に語彙分析に使用されると思います（私は非常に間違っている可能性があります）。追加の資料やリンクは大歓迎です。ありがとう ！

言語x^ay^bz^2(a+b) ( a>=0、b>=0 )の Context-Free Grammer を構築するにはどうすればよいですか。助けてくれてありがとう...

Sudkamp のLanguages and Machinesの問題 19.5では、文法が

強いLL(2)です。変数のFIRSTおよびFOLLOWセットは、Sアルゴリズム 19.5.1 (p. 583、第 3 版) を使用して計算されます。

Sルールの長さ 2 の先読みセットが、 の長さ 2 の先読みセットを分割しないことは明らかです。これは、 で構成される長さ 2 の先読みセットを生成Sするルールによります。S -> λFOLLOW(2)(S)

FIRSTの、FOLLOW、またはLA(2)セットの計算でエラーが発生した可能性がありますG。ただし、アルゴリズムを正しく実行したことにはかなりの自信があります。特に、それらの定義に戻ることができます。

問題は、なぜ文法が強いのかということですLL(2)。Sルールの長さ 2 の先読みセットが の長さ 2 の先読みセットを分割しない場合S、文法はstrongであってはなりませんLL(2)。しかし、本が期待する結論に達することはできません。私は何を理解していませんか？

言語を生成する CFG (コンテキストフリー言語) を定義します。

L={a^nb^mc^n | n,m>=0}

誰でも問題に対処する方法を教えてもらえますか?

私の理解では、L は次のような要素で構成されています: { aabbbcc } (n=2 および m=3 と仮定しました)

前もってありがとうヨアヒム

あなたの助けが必要です。私はこれらの作品を持っています：

チョムスキー正規形 (CNF) を適用する必要があります。

上記のルールを適用するには、次のことを行う必要があります。

1. ε 生成を消去する
2. ユニタリプロダクションを排除する
3. 不要な記号を削除

すぐに行き詰まります。その理由は、A がヌル可能シンボルであるためです (ε はその本体の一部です)。

もちろん、A 記号を削除することはできません。

誰かが最終的な解決策を得るのを手伝ってくれますか?

次の言語Lは決定不能ですか？

L = { M | Mはチューリングマシンの記述であり、 Mが最大kステップ後に停止するような長さkの入力xが存在します}

そうだと思いますが、証明できませんでした。停止性問題からの削減を考えてみました。

言語レベルの概念（通常、文脈自由、文脈依存など）を理解しようとしています。

これは簡単に調べることができますが、私が見つけたすべての説明はたくさんの記号であり、セットについて話します。2つの質問があります：

1. 正規言語とは何か、言語の違いを言葉で説明できますか？

2. 人々はどこでこのことを理解することを学びますか？私が理解しているように、それは形式的な数学ですか？私はそれを使用する大学でいくつかのコースを持っていました、そして家庭教師がちょうど私たちがそれを知っていると思ったのでほとんど誰もそれを理解しませんでした。どこでそれを学ぶことができますか、そしてなぜ人々はそれを非常に多くの情報源で知ることを「期待」されているのですか？教育にギャップがあるようなものです。

次に例を示します。

このセットに属する言語はすべて、アルファベット上の正規言語です。

言語はどのようにして何かを「超える」ことができますか？

形式言語とオートマトン理論のコース用の教育ツールの設計と実装を試すために、暇な時間を使うことを考えています。私は、OOPの実装が適切であるかどうか、もしそうであれば、以下に概説する設計の高レベルの改善を誰かが提案できるかどうかを判断しようとしています。

言語分析で明らかになった潜在的なクラスはたくさんあります。いくつか（そして私が基本的な何かを逃したかどうか私に知らせてください）は次のとおりです：文法; 非終端記号; ターミナル; 製造; 正規文法; 文脈自由文法; 状況依存文法; 無制限文法; オートマトン; 州; シンボル; 遷移; DFA; NFA; NFA-ラムダ; DPDA; PDA; LBA; チューリングマシン。

質問1：各種類の文法は、実装で独自のクラスを取得する必要がありますか、または包括的な文法クラスには、それがどの種類の文法であるかを判別するメソッドが必要です（たとえば、「isRegular（）」、「isContextFree（）」など）。 。） （より一般的には、ドメインモデルで少しだけ異なり、動作の点でのみ異なるクラスは、実装の継承によって表される必要がありますか、それとも単に異なる種類の動作を親クラスにプッシュする方がよいでしょうか？）

質問2：「シンボル」、「状態」、「非終端記号」などのようなものは、実装で独自のクラスを取得する必要がありますか、それともこれらはコンテナーによって支配される必要がありますか？ （より一般的には、ドメインモデルの非常に単純なクラスに、実装で独自のクラスを指定する必要があります（たとえば、拡張性のために）。それとも、コンテナークラスにプッシュする必要がありますか？）

質問3：トランジションは実装で独自のクラスである必要がありますか？その場合、各種類のオートマトンをサポートするためにサブクラス化する必要があります（状態が異なるだけでなく、何が起こるかも異なるため）移行中）？ （より一般的には、1つの子と別の子の間に全単射がある2つの抽象的な親クラスを持つことは良い習慣ですか...カップリング？）

結局のところ、これらの決定の多くは単なる設計上の決定であることに気づきましたが、皆さんがOOP設計のベストプラクティスについてどのように考えているかを知りたいと思います。さらに、純粋なOOP設計の質問として「より一般的な」質問をするだけではない理由は、この種のドメイン（言語とオートマトン）の経験がある人々からの特別な視点が欲しいからです。

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

1、「aa」と「epsilon」の 2 つの単語を認識できる NFA があります。したがって、この NFA が認識する言語 L1 は集合 {aa, epsilon} です。この言語の長さはどれくらいですか? |L1| です = 1? または |L1| = 2?

2、「aa」という単語を認識できる別の NFA があるとします。したがって、言語 L は集合 {aa} になります。形式言語では、イプシロンはすべての言語に属します。したがって、実際には L2 には集合 {aa, epsilon} であるイプシロンが含まれます。では、この言語 L2 の長さは? 1つか2つ？

ありがとう