問題タブ [automata]

私たちプログラマーが次のようなタスクのためにプログラムで使用する正規表現に気付きました

• メールアドレスの検証
• IP 検証
• ...

Automataで使用される正規表現とは少し異なります(私が間違っていなければ)。

ところで、私は IP 検証用の NFA を設計し、最終的には DFA を設計したいと考えています。次のような正規表現がたくさん見つかりました。

しかし、JFLAP を使用して NFA または DFA に変換することはできません。

私は何をすべきか？

DFAを生成できるプログラムを作成しました。しかし、DFAはわずかに正しくありません。つまり、正しい文字列を受け入れられない場合があります。

私の質問は、DFAを修正して、指定された正しい文字列を受け入れることができるアルゴリズムはありますか？

より正式には、

DFADが文字列strを受け入れないとします。

アルゴリズムが必要A、st D'= A（D、str）およびD'はstrを受け入れます

私が を持っている場合Σ={a}、 が を持っている単語は何Σ*ですか?

Σ*= {a,aa,aaa,aaaa.....}?

ありがとう

Σ*誰かがとの正確な違いを説明できますか? L*where Lis a language とΣis alphabet of the language L?

ありがとう

複数の文字列の最長の共通部分文字列を計算するために、接尾辞リンク (ここでは紙) を持つ factor-oracle を使用できますか? ここで、部分文字列とは、元の文字列の任意の部分を意味します。たとえば、「abc」は「ffabcgg」の部分文字列ですが、「abg」はそうではありません。

s12 つの文字列との共通部分文字列の最大長を計算する方法を見つけましたs2。たとえば、「$」など、文字列に含まれていない文字を使用して 2 つの文字列を連結することによって機能します。s次に、 lengthの連結文字列の各プレフィックスについて、i >= |s1| + 2その LRS (最長繰り返しサフィックス) の長さlrs[i]とsp[i](その LRS の最初の出現位置の終了位置) を計算します。最後に、答えは

私は、この方法を使用する C++ プログラムを作成しました。このプログラムは、|s1|+|s2| <= 200000オラクル因子を使用すると、ラップトップで 200 ミリ秒以内に問題を解決できます。

どちらの問題も suffix-array と suffix-tree を使用して高効率で解決できることはわかっていますが、factor oracle を使用して解決する方法はあるのでしょうか。factor oracle は簡単に構築でき (C++ で 30 行、suffix-array は約 60 行、suffix-tree は 150 行必要)、suffix-array や suffix-tree よりも高速に実行されるため、これに興味があります。

この OnlineJudgeで最初の問題の方法をテストし、ここで2 番目の問題をテストできます。

グッドデイスタックオーバーフロー。

私は正規表現の使用に慣れていないので、ここに問題があります。パスワードに4つの連続した文字が含まれている場合は、パスワードを確認する必要があります。これまで私がカバーしたのは数字に関するものです。これが私の正規表現です：

昇順の数字-^。？（？：0123 | 1234 | 2345 | 3456 | 4567 | 5678 | 6789）。$

降順の数字-^。？（？：9876 | 8765 | 7654 | 6543 | 5432 | 4321 | 3210）。$

これは数字に対してのみ機能します。私はこれがすでに正規表現でやり過ぎであることを知っているので、私は文字でそれをやりたくありません。私がそうするなら、それはあまりにもやり過ぎでしょう。

abcdblah//abcdのためtrue

helobcde//bcdeのためtrue

dcbablah//dcbaの本当の理由

heloedcb//edcbのためtrue

どんな助けでも大歓迎です。stackoverflowに感謝します。

同上。Java または C# が最適ですが、命令型言語であれば何でも構いません。

私が学生だった2000年に、私はオートマトン理論のコースを受講しました。このコースの演習では、基本的にGrail（http://www.csd.uwo.ca/Research/grail/）と呼ばれるUNIXコマンドラインツールを再プログラムしました。Grailを使用すると、正規表現または決定論的/非決定論的有限状態マシンを使用してファイルを読み込み、それらに一般的な理論的操作を適用できます。FSMの最小化、空のチェック、反転、FSMの積、FSMからRegEx、RegExからFSM、文字列を入力し、マシンをシミュレートするなど。

Grailは利用できるようですが、2002年以降開発されていないようです。したがって、私の質問：まだ活発に開発されている同様のツールについて誰か知っていますか？（つまり、現代のグレイル？）今日のクラスでは何が使われていますか？

私が探しているのは、stdinからFSMまたはRegExesを読み取り、操作を適用し、その結果をUnixの方法であるstdoutに出力して、独自のパイプを作成できるコマンドラインツールです。単純なFSMと正規表現で十分なので、プッシュダウンオートマトンやブチオートマトンのようなものは実際には必要ありません。

コマンドラインツールがない場合、優れたライブラリやグラフィカルツールはありますか？

ほとんどが単純な 16 状態のステート マシンであるコードのチャンクをデバッグしようとしていますが、遷移があまり単純ではない場合もあります (状態の変化が作用するデータは、2 つの C++ で約 200 バイトのデータです)。クラス）。

マシンが予想よりもずっと早く「最終」状態になっていることがわかりました。私はまだコードに精通していないので、さまざまな遷移パスをすばやく識別してデバッグしやすくする方法で、さまざまな状態と遷移を理解できるようになることを願っています。

このようなステート マシンをマッピングするための便利なツールやテクニックはありますか?

私がリバース エンジニアリングの観点からこれを行っていることは注目に値するかもしれないので、私が利用できるシステムの計画ドキュメントはありません。

特定の言語の CFG の作成についてサポートが必要です。

L = { x ∈ {a, b}* | x != x reversed }、つまり、Lは のすべての回文の補数ですL。

私は、特定の解決策よりも、この種の問題にどのようにアプローチするかに興味があります。