algorithm - クリーネスターのオートマタ

Question

オートマトンについて学んでいます。Kleene クロージャを使用したオートマトンがどのように機能するかを理解するのを手伝ってくれませんか? a、b、c という文字があり、ab*bac のように Kleene star で終わるテキストを検索する必要があるとします。

Answer 1

問題は、クリーネ閉包の意味よりも、オートマトンがクリーネ閉包をどのように処理するかということのようです。

たとえば、単純な正規表現を使用するとabc、それを認識するオートマトンを設計するのは非常に簡単です。各状態は、基本的に、これまでの式のどこにいるかを示します。状態0は、まだ何も表示されていないことを意味します。状態1は、それが見られたことを意味しますa。状態2は、それが見られたことを意味しますab。等。

クリーネ閉包の難しさは、のようなパターンがab*bcあいまいさをもたらすことです。オートマトンがを見てa、それに直面するとb、それがまたはに続く文字bの一部であるb*か、それともそれに続く文字bであるかがわかりません。また、さらに多くの記号を読み取るまでわかりません。

単純な答えは、オートマトンは、文字通り、どのパスが取られたかをまだ知らないことを意味する状態を持っているということです。

単純なケースでは、このオートマトンを直接構築できます。一般的なケースでは、通常、非決定性有限オートマトンと呼ばれるものを作成します。NDFAをシミュレートするか、パフォーマンスが重要な場合は、NDFAを決定性に変換するアルゴリズムを適用できます。アルゴリズムは基本的に、すべてのあいまいな状態を生成します。

Answer 2

Kleene スター ('*') は、その文字を好きなだけ (0 以上) 出現させることができることを意味します。 a*任意の数の a に一致します。

(ab)*文字列「ab」の任意の数に一致します

式で実際のアスタリスクと一致させようとしている場合、それを記述する方法は、使用している正規表現の構文に完全に依存します。一般的なケースでは、バックスラッシュ\がエスケープ文字として使用されます。

\*アスタリスクに一致します。

最後にパターンを認識するには、連結を使用します。

(a U b)*c*は、末尾に 0 個以上の 'c' があり、その前に任意の数の a または b が続く任意の文字列に一致します。

Kleene スターで終わる一致するテキストについては、繰り返しますが、文字列を 0 回以上出現させることができます。

ab(c)*- 可能な一致: ab、abc abcc、abccc など。

a(bc)*- 可能な一致: a、abc、abcbc、abcbcbc など。

Answer 3

英語で ab*bac という表現は次のようになります。

a の後に 0 以上が続く b の後に bac が続く

strings that would evaluate as a match to the regular expression if used for search

abac
abbbbbbbbbbac
abbac

strings that would not match

abaca //added extra literal
bac //missing leading a

前の回答で述べたように、実際に * を検索するには、実装固有のエスケープ文字が必要であり、選択した言語/ライブラリの知識が必要です。