regex - a が b に決して隣接しないような、a、b、c 上の言語の正式な正規表現

Question

aがbに決して隣接しないように、文字a、b、cを含む言語の正規表現クエリを作成しようとしています。

交互 (プラス)、連結、繰り返し (乗算) 演算子だけを使用して実行できますか?

L = w は {a,b,c}* に属し、a は決して b に隣接しません

Answer 1

(形式言語理論を十分に思い出せるか見てみましょう。)

このような正規表現は、次のような DFA を使用して構築できます。

A = aA + cC + F      // only a or c can follow a
B = bB + cC + F      // only b or c can follow b
C = cC + aA + bB + F // any char can follow c

ここAで、Bとは、とがそれぞれ前の文字だったCときの状態を表します。どのキャラクターも従うことができるので、開始状態にすることができます。最終的な終了状態 (文字列の終わり) です。abccCF

この DFA は、次のような正規表現に変換できます。

A = a*(cC+F) // eliminate recursion
B = b*(cC+F) // eliminate recursion

C = cC + aA + bB + F
  = cC + aa*(cC+F) + bb*(cC+F) + F       // substitute A and B
  = (c + aa*c + bb*c)C + aa*F + bb*F + F // regroup
  = (c + aa*c + bb*c)*(aa*F + bb*F + F)  // eliminate recursion
  = (c + aa*c + bb*c)*(aa* + bb* + e)F   // regroup

したがって、式は次のようになります。

(c + aa*c + bb*c)*(aa* + bb* + e) // e being the empty/null string

または、非公式の正規表現形式で:

(c|a+c|b+c)*(a+|b+)?

これは次のように短縮できます。

(a+c|b*c)*(a*|b*)