15

問題

参照セットに存在するすべての文字が他の文字列に存在するかどうかを確認できる正規表現を作成しようとしていますが、奇数 (1、3、5、...) のみです。

問題を表すDFAの (非常に) 粗い画像を次に示します。

奇数の A および B の DFA

私の（壊れた）ソリューション

私は有限集合 を使い始めたので、基本的に「文字列に奇数の と奇数の の{a, b}両方があるか?」をチェックします。ab

残念ながら、私は自分で遠くまで行くことはできませんでした。このスレッドは、この概念に非常に似ていますが、から回答を得ることができませんでした(aa|bb|(ab|ba)(aa|bb)*(ba|ab))*(b|(ab|ba)(bb|aa)*a)。（私はそれがどのように機能するかを理解していますが、存在する両方のアイテムの奇数をチェックするために変換する方法は理解していません。）

これが私がこれまでに思いついたものです: ^((ab|ba)(bb|aa)?|(bb|aa)?(ab|ba))+$. これは基本的に、orの後にaborbaが続くbbかどうかをチェックします。(この逆も行い、最初に二重文字をチェックします。) これは無限に繰り返すことができます。私が抱えている問題は、文字列と一致するように調整できないように見えることです。aaabbaabaaabbbbaaababbbbaababbaa

さらに、上記の方法は、たとえば、を考慮して動的に調整することはできませんが{a, b, c}、最初の問題を解決するためにこれを放棄しても構わないと思っています。

テスト

これが私のテスト文字列と目的の出力です。括弧内に理由を示します。

"ba"      # True (1a, 1b)
"abbb"    # True (1a, 3b)
"bbba"    # True (1a, 3b)
"bbab"    # True (1a, 3b)
"ababab"  # True (3a, 3b)
"bbaaba"  # True (3a, 3b)
"abb"     # False (2b)
"aabb"    # False (2a, 2b)
"aabba"   # False (2b)
""        # False (0a, 0b is "even")
"a"       # False (0b is "even")
"b"       # False (0a is "even")

質問

それで、これは正規表現を介して可能ですか？それとも、正規表現は DFA よりも制限されていますか? 基本的なループで実行できることは承知していますが、これは私が目指していることではありません。

4

3 に答える 3

11

正規表現はDFAよりも限定的ではありません。実際、それらは同等です。(後方参照を持つ Perl スタイルの「正規表現」は厳密にはより強力であるため、「通常」ではありません。)

a文字列にsのみが含まれている場合、正規表現を簡単に記述できます。

a(aa)*

また、間に他の文字が出現する可能性がある場合でも、それらの文字を単に無視することでそれを行うことができます。

[^a]*a([^a]*a[^a]*a)*[^a]*

正規表現は DFA と同等であるため、個々の文字ごとに DFA があります。実際、それは非常に簡単です：

 [^a] _      [^a] _
     / \         / \
     | v   a     | v
---> (0) -----> ((1))
         <-----
            a

状態 (0) は開始状態 (「偶数aの が見られた」) であり、状態 ((1)) は唯一の受け入れ状態 (「奇数aの が見られた」) です。が表示された場合はa、別の状態に移動します。他の文字については、同じ状態のままです。

DFA の優れた点は、コンポーザブルであることです。特に、それらは交差点の下で閉鎖されています。つまり、「奇数の s を含む文字列」という言語を認識する DFA と、「奇数のas を含む文字列」という言語を認識する別bの DFA がある場合、それらを組み合わせて、これら 2 つの言語の共通部分、つまり「奇数のa' と奇数の ' を含む文字列b」です。

アルゴリズムについては詳しく説明しませんが、この質問にはかなり良い答えがいくつかあります。結果の DFA には 4 つの状態がありaます。bab

また、DFA は正規表現と同等であるため、それらの文字列に正確に一致する正規表現も存在します。繰り返しになりますが、アルゴリズムの詳細については触れませんが、こちらの記事でかなり詳しく説明しています。便利なことに、面倒な作業を行うための Python 3 コードも付属しています。

>>> from fsm import fsm
>>> a = fsm(
      alphabet = {'a', 'b'},
      states = {0, 1, 2, 3},
      initial = 0,
      finals = {3},
      map = {
        0: {'a': 1, 'b': 2},
        1: {'a': 0, 'b': 3},
        2: {'a': 3, 'b': 0},
        3: {'a': 2, 'b': 1}
      }
    )
>>> str(a.lego())
'a*(ab|b(ba*b)*(a|ba+b))((a|ba+b)(ba*b)*(a|ba+b)|ba*b)*'

ライブラリにバグがあるか、間違って使用しているa*可能性があります。しかし、考えはわかります: 理論的には可能ですが、これに正規表現を使用したくないのです!

于 2012-09-14T21:00:18.817 に答える
8

これを行う1つの方法は、先読みを使用して各条件を順番にアサートすることです。

^(?=[^a]*a(?:[^a]*a[^a]*a)*[^a]*$)(?=[^b]*b(?:[^b]*b[^b]*b)*[^b]*$)(.*)$

これがあなたの例のデモです。（\nデモのsはプレゼンテーション用です。また、(.*)$キャプチャではなく、一致をテストするだけでよい場合は、を削除できます。）

間もなく説明を追加します。

説明

半分だけ見る必要があります：

(?=  [^a]*a  (?:[^a]*a[^a]*a)  *  [^a]*$  )
|    |       |                 |  |
|    |       |                 |  Only accept non-'a's to the end.
|    |       |                 |
|    |       |                 Zero or more of these pairs of 'a's.
|    |       |
|    |       Strictly a pair of 'a's.
|    |
|    Find the first 'a'.
|
Use a lookahead to assert multiple conditions.
于 2012-09-14T20:37:45.953 に答える
4

はい：

^(?=b*(?:ab*ab*)*ab*$)(?=a*(?:ba*ba*)*ba*$)

説明：

^             # Start of string
(?=           # Assert that it's possible to match
 b*           # any number of 'b's
 (?:ab*ab*)*  # followed by an even number of 'a's with optional 'b's in-between
 ab*          # followed by one 'a' and optional 'b's
 $            # until the end of the string.
)             # End of lookahead
(?=a*(?:ba*ba*)*ba*$)  # Same thing, vice versa

正規表現自体はどの文字とも一致しないため、一致結果として常に空の文字列が取得されます（これは一致結果として取得するのとは異なりますNone）。

>>> import re
>>> re.match("^(?=b*(?:ab*ab*)*ab*$)(?=a*(?:ba*ba*)*ba*$)", "ab")
<_sre.SRE_Match object at 0x00000000022AA7E8>
>>> re.match("^(?=b*(?:ab*ab*)*ab*$)(?=a*(?:ba*ba*)*ba*$)", "aab")
于 2012-09-14T20:39:02.240 に答える