問題タブ [formal-languages]

aがbに決して隣接しないように、文字a、b、cを含む言語の正規表現クエリを作成しようとしています。

交互 (プラス)、連結、繰り返し (乗算) 演算子だけを使用して実行できますか?

L = w は {a,b,c}* に属し、a は決して b に隣接しません

形式言語（Aho's、Hopcroft）は独学で学んでいますが、正規表現が苦手です。

私は単純なタスクに取り組むことができましたが、これは少なくとも私にとっては挑戦でした. ここまで数えられない場合の解決方法、私はこの種の計算に慣れていません。
正規表現として表現できるほど答えを一般化できるプロパティまたは何かがあるに違いありません。

これまでのところ、少なくとも 2 ～ 3 のケースが存在する可能性があると考えています。

• sum=3k の場合、mod3=0 を合計します。
• sum=3k+1 の場合、mod3=1 を合計します。
• sum=3k+2 の場合、mod3=2 を合計します。

しかし、合計が発生するには多くの組み合わせがある可能性があるため、正規表現が従わなければならないパターンを見つけることができないことに気づきました。

exの文字列。{122211}0（中括弧は読みやすくするためのものです）{sum=3k}0exの文字列から合計が「10」の場合、それが保持されるため、最後にゼロがあります。{1222111}1場合によって{sum=3k+1}は、最後にある必要があるなどです。

これは問題に取り組むための正しい道であるかもしれませんし、そうでないかもしれませんが、どんな提案も歓迎します。どんな助けも大歓迎です。

正規表現をNFAに変換するアルゴリズムがあることを知りました。

しかし、NFA を正規表現に変換するアルゴリズムがあるかどうか疑問に思っていました。あるとすれば、それは何ですか？

ない場合は、すべての NFA が正規表現に変換できるかどうかも疑問です。正規表現で表現できないNFAはありますか?

ありがとうございました！:D

クラスの宿題に取り組んでいて、この質問に行き着きました：

次の正規表現のそれぞれについて、表現で定義された言語にない最小限の長さの文字列を指定します。

1. (bb)*(aa)*b*
2. a*(bab)*∪b∪ab

私は最初のものについてのみ助けを得ようとし、2番目のものを理解できるかどうかを確認します. 私が知っていることは次のとおりです。Kleene * は、0 個以上の可能な要素を示します。集合の和集合は、集合 a と集合 b のすべての要素を含み、要素を繰り返さない集合です。ラムダを挿入することから始まる最初の問題に取り組むと、次のようになります。

1 回目: bbaab
2 回目: bbbbaabaabbaabbbbaab
3 回目: bbbbbbaabaabbaabbbbaabaabbbbaabaabbaabbbbaabbbbbbaabaabbaabbbbaab

長さが 0 から 5 の文字列よりも正しく実行している場合、言語には含まれていません。私はこれを正しくやっていますか？

L1 = {a^ib^j | i,j>=0 }

私の試み：

答えを確認する方法がありません。これは正しいですか?

これはウィキペディアの決定可能性の定義です

計算可能性理論では、決定不可能な問題は、特定のはい/いいえの答えが必要なインスタンスのファミリで構成されているため、入力として問題のインスタンスが与えられた場合、有限数の後に必要な答えを終了して出力するコンピュータープログラムはありませんステップの。より正式には、決定不能な問題とは、言語が再帰集合でない問題です。

再帰セットは、再帰的に列挙可能なセットのサブセットです。再帰セットの外にある、再帰的に列挙可能な言語がいくつかあります。では、再帰的に列挙可能な言語が決定不能ではないのはなぜでしょうか?

MATLAB 言語の基本的なサブセットを C# や C++ などに変換するレクサー ジェネレーターを作成したいと考えています。これを行うために、MATLAB の正式な文法を含むドキュメントを見つけたいと考えています。これについて少し時間をかけて調査したところ、Mathworks はそれを提供していないようです。

そのようなドキュメントをどこで見つけることができるか知っている人はいますか?

この言語が規則的かどうかを証明するにはどうすればよいですか?

L = {a ⁿ b ⁿ : n≥1} 和集合 {a ⁿ b ⁿ⁺² : n≥1}

文法階層だけでなく、一般的な形式言語（文字列のセット）の記述を扱う数学的理論を探しています。