問題タブ [kleene-star]

(a|b)*とはどう違いa*b*ますか？クリーネのスターとパターンの例をもっと見せてもらえますか? Google で非常に多くのサイトを検索しましたが、このトピックに関する結果はほとんど返されません。PHPの正規表現がどのように機能するかを理解しようとしているので、とても感謝しています。

クリーネ閉包演算子（例：（ab）*）のみを含む正規言語Lが与えられた場合、2つの非正規言語の連結によってLを生成できる可能性があることを知りたいですか？私は、Lが2つの正規言語の連結によってのみ生成できることを証明しようとしています。

ありがとう。

特定の正規表現のセットを単一の NFA に変換していますが、いくつか問題があります。「ab.*c」(「a」、「b」、任意の数の文字、および「c」の一致を表す) などの正規表現を変換するにはどうすればよいですか?

私の最終的な目標は、単一の NFA を DFA に変換することです (そのためにサブセット構築アルゴリズムを使用しています)。

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

私はATMを学んgrepでいますが、クリーネ閉包のメタ文字の働きを理解するのに苦労しています。マニュアルページには、*前の文字と0回以上一致することが記載されています。test次の内容のファイルを使用しています

grep 'a*' test0個以上のオカレンスに一致する必要があり、説明されているように、出力のファイルaのすべての行を出力します。testこのドキュメントではさらに、メタ文字を一致させるには、メタ文字の*前に円記号を付けてエスケープする必要があると説明しています\。しかし、とからの出力grep '*' testはgrep '\*' test同じです。出力：前に付けずに自分自身を照合するの*a はなぜですか？*\

との間に違いは(aa)*あり(a*a*)ますか？

分配法則はありますか？

テスト文字列に一致するように、特定の正規表現からDFAを作成しました。発生する場合があり.*ます。（たとえば.*ab）。ここで、マシンが状態1にあるとします。DFAでは、 .*すべての文字のそれ自体への遷移と、状態1から「a」へのaの別の遷移を指します。テスト文字列に「a」が含まれている場合、状態1から、マシンはDFAでは不可能な2つの状態に移行する可能性があるため、遷移となる可能性があります。

私は計算可能性に関する本でこれを読みました：

(クリーネの定理) ある言語が正則であるのは、結合、連結、反復の 3 つの操作を有限回数適用することによって有限言語から得られる場合に限ります。

私は「有限言語」に苦労しています。

この言語を考えてみましょう:L = a*

有限ではありません。{0, a, aa, aaa, ...}明らかに無限集合（0＝空の文字列）である集合です。

無限の言語ですね。つまり、「無限集合」とは「無限の言語」ということですよね？

明らかにa*正規言語です。そしてそれは無限の言語です。したがって、クリーネの定理により、正規言語になることはできません。矛盾。

よくわかりません。私は「有限言語」が何を意味するのか分からないと思います。

私は正規表現を学んでいるので、自分の理解が正しいことを確認したいだけです。

01*0 の後に 1 の 0 回以上の繰り返しが続くことを
1* + 01*意味します。 は、1 の 0 回以上の繰り返しまたは 0 の後に 1 の 0 回以上の繰り返しが続くことを意味します。

私は正しいですか、それとも欠けているものがありますか? ありがとう。