私はドラゴンの本を読んでいて、いくつかの正規表現の練習で立ち往生しています、それは興味をそそられます、誰かが助けることができますか？次の言語の正規表現を記述してください。
問題1：
偶数のaと奇数のbを持つaとbのすべての文字列。
問題2：
サブシーケンスabbを含まないすべての文字列。（sのサブシーケンスは、0個以上の連続した位置を削除することによって形成される任意の文字列です。segbaanはバナナのサブシーケンスです。）
問題3：
繰り返される数字のないすべての数字の文字列（繰り返される数字は必ずしも連続しているとは限りません）。
問題4：
最大で1桁の数字が繰り返されるすべての数字列（繰り返される数字は必ずしも連続しているとは限りません）。
そして、私たち両方がそれをよく理解できるように、POSIX文法を使用してください。また、それらを達成するために、3つの基本的な言語操作、つまり、和集合、連結、およびクロージャーしか使用できないのではないかと思います。
ありがとう。
厳密な正規表現（連結、結合、クロージャ）がある場合は、それをPOSIX正規表現に変換できます。POSIX正規表現を使用している場合は、より洗練された正規表現エンジンに変換できます。
仮定（これを最初に読んでください）
この回答は、JavaScript正規表現のサポートレベル（先読みはあるが後読みはない）を前提としていますが、例外なくすべての文字に一致することも前提としてい.ます。ここでの正規表現は、文字列全体がパターンと一致していることを前提としています。
問題1
^(?=(?:b*ab*a)*b*$)(?=(?:a*ba*b)*a*ba*$)[ab]*$
この問題のDFAを構築することは可能であるため、連結、和集合、および閉包のみの正規表現が存在します。（DFAの状態の数字は、aとbの数のパリティを示します）。
ただし、厳密な正規表現を導出するのは非常に面倒です。見回すと、考え方が簡単になります。
(?=(?:b*ab*a)*b*$)は先読みであり、（との効果により^）文字列全体が一致$することを確認します。これは、偶数の数を意味し、オプションで、その間と周囲に有限の数があります。(b*ab*a)*b*ab(?=(?:a*ba*b)*a*ba*$)は先読みであり、文字列全体が一致することを確認します(a*ba*b)*a*ba*。これは、奇数bの数を意味し、aオプションで、その間と周囲に有限の数があります。文字列が上記の正規表現で指定されたプロパティを満たしていることを確認するには、文字列を3回通過する必要があります。
POSIX正規表現を使用すると、これら2つの正規表現に対して文字列を2回テストして、2つのプロパティをアサートできます。
^(b*ab*a)*b*$
^(a*ba*b)*a*ba*$
ただし、厳密な正規表現が存在し、実行可能であるため、プロパティを満たす文字列に一致する単一のPOSIX正規表現が存在します。DFAを厳密な正規表現に変換する方法については、この投稿をお読みください。
問題2
^(?!.*a.*b.*b).*$
先読みで、サブシーケンスに一致する方法がないことを確認しますabb。
アルファベットが指定されていないため、すべての文字と解釈される可能性があるため、厳密な正規表現でこれを記述することは可能ですが、実用的ではありません。ただし、否定文字クラスが許可されている場合は、簡単に記述できます。
([^a]*a[^b]*b[^b]*|[^a]*a[^b]*|[^a]*)
（上記は厳密な正規表現ですが、POSIX正規表現として簡単に書き直すことができます）
交互に（右から左に）3つの項目は、DFAの3つの状態に対応しaます。がありますaが、先はありませんb。がありa、bその後のどこかに続きますが、まだ2番目が見つかりませんb。DFAには別のトラップ状態（ゴール状態への遷移の可能性はありません）があります。サブシーケンスabbが見つかりました。
問題3
^(?!\d*(\d)\d*\1)\d+$
ネガティブ先読みを使用して、繰り返されている文字を見つけることができる一致がないことを確認します。これは数字の文字列であるため、少なくとも1桁を指定して、空の文字列を一致させないようにします\d+。この正規表現の重要なポイントは、キャプチャされたグループと後方参照の使用です。
繰り返しになりますが、これには厳密な正規表現がありますが、そのような正規表現を書くことは、可能なすべての一致を1つずつリストすることとほぼ同等であるため、実用的ではありません。可能な一致の合計がありますSum [i = 1..10] ( 10! / i! )（先行0が許可されます）。次の文字が許可されるかどうかは、これまでに処理されたすべての文字に大きく依存するため、これを回避する方法はありません。
キャプチャグループを無効にするメカニズムがないため、これはPOSIX正規表現でも実用的ではありません。
問題4
これのためのより良い正規表現を思い付くことができません...
^(?!(?=.*(.).*\1).*((?!\1).).*\2)(?!.*(.)(?:.*\3){2})\d+$
失敗する条件は2つあります。数字が2回以上繰り返されるか、2つの異なる数字が繰り返されるかのいずれかです。
(?!(?=.*(.).*\1).*((?!\1).).*\2)2つの異なる数字が繰り返されていないことを確認します。この先読み(?=.*(.).*\1)は、繰り返されている1つの文字を（少なくとも2回）選択し、.*((?!\1).).*\2以前にチェックされたものとは異なる数字を選択します。これは、のために((?!\1).)、繰り返された数字を見つけようとします。(?!.*(.)(?:.*\3){2})数字が最大2回繰り返されていることを確認します。内部のパターンは、数字の3つのインスタンスに一致しようとします。これには問題3と同じ問題があるため、厳密な正規表現またはPOSIX正規表現を記述することは実用的ではありません。興味がある場合は、Sum [i = 1..10] ( 10! / i! ) + Sum [i = 1..10] ( (i + 1)C2 * 10! / i! )一致する可能性があります（先行ゼロが許可されます）。
問題3と4、特に問題4の場合、文字列に数字のみが含まれていることを確認してから、数字を並べ替えてループし、繰り返し数字がないかどうかを確認する方が実用的です。