問題タブ [formal-languages]

単語がキーワード (下品など) の大きなリストに含まれているかどうかを判断したいと思います。これらを書き換えるにはいくつかのルールが必要なので、パーサーが適切な解決策である必要があります (私の知る限り高速である必要があります)。言葉。

私の質問は、（可能であれば）次のような文法規則に追加する方法です。

• 単語のすべての文字の後にアスタリスクを追加します

• リート言語

• word + -ing、word +-ed などの単純なルール

（これにはチュートリアルがあるはずですが、見つけることができませんでした。）

注:このシステムは管理者にのみ通知するため、100% 正確である必要はありません。

または、より良い別のアプローチをお勧めできますか？

ありがとう！

文字列の括弧のバランスをチェックするために、次のプログラムを作成しました。

以下にデータの例を示します。

このプログラムは明示的な再帰の最も基本的な構成要素のみを使用するため、私がまだ気付いていない言語機能を含む、より短く、より高度なアプローチがあるかどうか疑問に思いました。

さて、いくつかの回答とコメント（および私自身の考え）から次の解決策を抽出しました。

何よりも、そうです、これはコースワークからのものであり、私は別のプロジェクトを扱っている間、散発的にそれに取り組んできました。

言語は、（端子'a'および'b'の）文字列で構成されます。ここで、aの数=bの数です。上記の言語を定義する文法の生成規則を見つけようとしています。

より正式には、L（G）= {w | Na（w）= Nb（w）}

したがって、L = {ϵ、ab、aabb、abab、abba、bbaa、...など}のようになります。

ヒント、または解決策に関連する問題でさえ、現在の問題をよりよく理解するのに役立つ可能性があります。

私はそれらのそれぞれがどのように相互に変換できるかを知っていますが、それらのアプリケーションが何であるかを実際には理解していません。通常のインフィックス操作は非常に読みやすいですが、どこで失敗するので、プレフィックスとポストフィックスの表記が開始されます。

アルファベット{a、b}で次の正規表現の言語を見つけるにはどうすればよいですか？

編集：私が狂ったように反対票を投じる前に、誰かが解決策だけでなく、これらの問題を解決するためのステップを教えてくれれば幸いです。たぶん、私が自分で残りを行うことができるように、私を1つに案内することさえあります。

ありがとう！

質問は、アルファベット {a, b} の上に部分文字列 aba を含む文字列の正規表現を見つけることを求めています。

これは、正規表現が次のようになるように、何でも aba に先行/先行できることを意味しますか?

または、質問は単に探しています:

注: U は結合を意味し、* は 0 回以上を意味します。

私の教科書によると、L1 = A* - L1 の補集合は、L1 が正規言語である限り、正規言語です。
A* には、Context Free 言語、Context Sensitive 言語、Recursively Enumerable 言語も含まれていませんか? A*-L1 にはそれらもすべて含まれますね。では、どうすれば定期的になることができますか？
有限ステート マシンの表現の下で、補語がまだ通常の言語である理由がわかりました。しかし、その背後にある理論を理解することはできません。

また、 A* - L1 = A* 交差補数(L1) . 補数によって定義されるもので補数を定義することは、トートロジーではありませんか? それがどのように有効なのか、私にはよくわかりません。

ありがとう。

私は次の文法を扱っています：

私は L(G) を見つける必要があります。問題は、文法の単語が次の形式であることがわかりました: a で始まり b で終わる、または b で始まり a で終わる、そしてこれらの文字の間の組み合わせの 1 つ: ab、ba、aaba、あばあ; 次の単語は、これらの 4 つの組み合わせのいずれかを真ん中の a と b の間に挿入することによって形成されます..しかし、これをどのように正式に表現できますか? つまり、私が知る限り、L(A) = a^n S a^n であり、w が L(G) に属している場合、w 反転も L(G) に属しています。正規表現として表現しようとしましたが失敗しました...誰か助けてもらえますか?

ありがとうございました。

文脈自由および文脈依存言語での文脈という用語はどういう意味ですか？変数は複数のコンテキストを持つことができますか？特定の値を特定のメモリアドレスに格納する必要がある場合、メモリアドレスのコンテキストにどのように影響しますか？また、変数を更新したい場合、変数のコンテキストはどのように変更されますか？