Regex przyjmuje ciąg znaków spełniający wymóg "(" a "* N - 'b' * M)% 3 = 0" - regex

idąc dalej z tym tematem, byłempróba napisania wyrażenia regularnego, które: „z alfabetu {a, b} akceptuje ciąg znaków tylko wtedy, gdy wystąpienie„ a ”minus wystąpienia„ b ”można podzielić przez 3.” Czy ktoś mógłby mi pomóc poradzić sobie z tym? Wiem, że powinienem udzielać DOWOLNEGO wkładu, aby pomóc w rozwiązaniu tego problemu, ale nie mam pojęcia.

Może tylko dlatego, że prawdopodobnie powinien zacząć(aaa) jako podstawa, a następnie rozwinąć dalej o kolejne „pary” „a” si „b”, ale nie wiem, jak to zrobić, aby rozwinął się jak „(aaa) aaabbb”, a nie jak „(aaa) ababab” .

Odpowiedzi:

Problemy wyrażenia regularnego oparte na obliczeniach najłatwiej jest przedstawić za pomocą automatów skończonych i zredukować do jednego wzorca.

Z trzema węzłami, po jednym dla każdej wartości modułowej; Zdefiniuj przejścia jako to, co dzieje się z wartością modułową, kiedy a lub b są przetwarzane.

Następnie zwinąć jeden węzeł, zastępując każdą ścieżkę przez węzeł pojedynczymi przejściami.

• 0->2->0 → 0->0 (ba)
• 0->2->1 → 0->1 (bb)
• 1->2->0 → 1->0 (aa)
• 1->2->1 → 1->1 (ab)

Powtórz dla innego węzła.

• 0->1(->1)*->0 → 0->0 ((a|bb)(ab)*(b|aa))

Ostateczny wzór to: (ba|(a|bb)(ab)*(b|aa))*