問題タブ [automaton]
For questions regarding programming in ECMAScript (JavaScript/JS) and its various dialects/implementations (excluding ActionScript). Note JavaScript is NOT the same as Java! Please include all relevant tags on your question; e.g., [node.js], [jquery], [json], [reactjs], [angular], [ember.js], [vue.js], [typescript], [svelte], etc.
regular-language - 偶数の 0 を含む文字列の正規言語ポンピング補題
偶数のゼロを含む文字列が a) 文脈自由 b) 通常かどうかを調べる
a) CFL のポンピング補題を使用すると、e(0 n )e(0 n )eと表すことができます。だから、それはCFLです。
(00)*b)正規表現のように表すことができます。だから、正規語だと思います。しかし、正規言語のポンピング補題を使用して同じことを証明することはできません
どんな助けでも大歓迎です。ありがとう！！
regex - 多数の文字列で正規表現をテストする
私はたくさんの文字列を持っています (多分 50k-1M くらいで、どれも長すぎず、1-20 文字かもしれません)。これで任意の RegExp を取得し、一致するすべての文字列のリスト/イテレータを返す必要があります。これは、できるだけ速くする必要があります。
それを行うのに適したインデックス構造は何ですか?
現在、文字列の文字にツリーを構築しています。そして、RegExp を決定論的オートマトンに変換します。そして、そのオートマトンと木との交点を計算します。それは速いアプローチのように見えますが、他の可能性について疑問に思います。
追加の課題は、Unicode/UTF8 をサポートすることですが、今のところ、この質問をその部分に集中させたくありません。
string - サフィックスオートマトンとは？
接尾辞オートマトンとは正確には何なのか、それがどのように機能し、接尾辞ツリーや接尾辞配列とどのように異なるのかを説明してもらえますか? すでにウェブで検索してみましたが、明確で包括的な説明に出くわすことができませんでした。
私が求めていたものに最も近い次のリンクを見つけましたが、それはロシア語であり、英語への翻訳は理解しにくかった.