問題タブ [regular-language]

この言語が規則的かどうかを確認するタスクが与えられました。

これに対する正規表現も、決定論的 (またはそうでない) 有限状態オートマトンも見つかりません。一方、ポンピングの補題定理で逆を証明する方法は見つかりませんでした。

何か案は？

タイプ 3 グラマーはこれらの両方のプロダクションを持つことはできないというメモを読みました

ここで、A、B は非終端記号であり、a は終端記号です

タイプ 3 については十分に知っていますが、上記が理解できません。

上記のオートマトンの場合、私の教科書で与えられている正規表現は次のとおりです。

私はこれを導き出すのに苦労しています...以下はそれに対する私の試みです：

私は間違っているか、本に記載されている形式に単純化することができません。誰かが私をここに案内してくれたり、間違いを指摘したり、段階的に説明してくれませんか？

本当にありがたいです。

以前、私はここで、有限オートマトンの遷移グラフを正規表現に変換するための助けを求める質問をしました。

この有限オートマトンの正規表現を理解（および形成）する

ユーザーPatrick87のおかげで、探していたヘルプを見つけることができました。私はまた、彼が彼の答えで言及した次のリンクを読みました：

http://krchowdhary.com/toc/dfa-to-reg-exp.pdf

これは、正規表現を見つけるための3つのアルゴリズム手法を説明しています。直感的に、私はBrzozowski代数法に惹かれ、上部に記載されている前回の投稿で助けを求めていたFAを解決しようとしました。

以下は私がFAのために作った特性方程式です。私が間違っている場合は教えて訂正し、正しい方向に向けてください！

R1 = bR2 + aR3

R2 = aR2 + bR4

R3 = aR3 +bR2+λ

R4 = aR4 + bR3

これらは正しいですか？はいの場合、すべてのRiはRjに関してi≠jであるため、どのように置換を行うのですか。

助けてください：D

For example, in an assignment given to me, we were asked to find out if two regular expressions are equal or not.

My question is how is one supposed to do that? If I draw the transition graphs for both and then run a few strings through it and show that both of the TGs are able to accept it, is that a sufficient proof ? If not, how do I do it? Is there a mathematical/axiomatic approach towards this?

Thanks in advance.

EDIT: There is another thing that I'd like to clear which is kind of related to this question. Are the two FAs depicted in the photo below the same?

i.e. Are (1) and (2) in the above picture the same?

Haskellを使用したファイル解析での作業で、との両方を使用していData.Attoparsec.Char8ますData.ByteString.Char8。： -/[]_のような記号を含むことができる式を解析したい。（マイナス、スラッシュ、ブラケット、アンダースコア）。

私は次のパーサーを書きました

...しかし、期待どおりに機能しません。

誰かが私を助けることができますか。

御時間ありがとうございます。

私は次の正規表現を取得しようとしています：

• 「＃」と「＃」から末尾の「\ t」（空白）までのすべてのテキストを取得します。

これまでのところ：

これは間違っているようですか？それを修正するにはどうすればよいですか？

形式言語（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}は、最後にある必要があるなどです。

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

私の本は、正規文法と正規言語について似ていますが、わずかに異なる説明をしています。私はそれが間違っているとは思いませんが、正規言語は正規文法と同じものですか？私の本の定義は次のとおりです。すべてのプロダクションがV->aWまたはV->Waであり、V、W非終端記号または終端記号、「a」終端記号が付いている場合、文法は正規文法です。Wは空でも同じでもかまいません。 Vの。

私の文字列はこのようなものです

結果が次のようになるように、文字列の一部をどのように置き換えることができますか

sfdfdsfdsfgfdgdfgkknfkgdfdsfd

つまり、太字のコンテンツは削除する必要があります。